Leetcode日记：78&90.子集

78.子集

问题1

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, 0);
    return list;
}

private void backtrack(List<List<Integer>> list , List<Integer> tempList, int [] nums, int start){
    list.add(new ArrayList<>(tempList));
    for(int i = start; i < nums.length; i++){
        tempList.add(nums[i]);
        backtrack(list, tempList, nums, i + 1);
        tempList.remove(tempList.size() - 1);
    }
}

90.有重复子集

问题2

Given a collection of integers that might contain duplicates nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

1
2
3
4
5
6
7
8
9
10
Input: [1,2,2]
Output:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<List<Integer>> subsetsWithDup(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, 0);
    return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int start){
    list.add(new ArrayList<>(tempList));
    for(int i = start; i < nums.length; i++){
        if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates
        tempList.add(nums[i]);
        backtrack(list, tempList, nums, i + 1);
        tempList.remove(tempList.size() - 1);
    }
}

分析

树状图

算法流程树状图
算法流程树状图

回溯算法

  1. 思路
    这道题也是一个很明显的穷举类型的题目，搜索空间可以用树表示，而且可以采用递归，所以我们决定采用回溯算法。
  2. 结构
    • 条件：数组从第一个元素读到最后一个元素
    • 迭代：一个元素放好之后递归继续进行迭代，过程如树状图所示
    • 结束：当读到最后一个元素，说明之前所有子集已收集完毕。
  3. 关于重复元素，判断语句多了一个start && nums[i] == nums[i-1]因为是子集问题，不用像考虑排列组合那样，这道题直接将重复元素略过就可以了。

更多回溯算法

更多关于回溯算法的问题请转到回溯算法标签