xiedaxia1hao
commented
3 years ago 模版题: 78. Subsets
Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order.
这种要求我们求子集的题目，又是return all possible subsets，我第一反应就是要用backtrack来做，因为backtrack的特点就是穷尽所有可能的情况来找到满足条件的解。
这题还有一种思路，就是用BFS来做，在实现上会比backtrack稍微简单点，也更直观一点。这一题我会先用BFS来做一遍，然后再提供backtrack的解法。
那这题如何用BFS来做呢？
举个例子，对于集合[1, 5, 3] 来说，我们可以：
- 先创建一个空集合，加入到我们的队列里: [[]]
- 把第一个数字（1）加到该队列的所有子集合里：[[], [1]]
- 把第二个数字（5）加到该队列的所有子集合里：[[], [1], [5], [1,5]]
- 把第三个数字（3）加到该队列的所有子集合里：[[], [1], [5], [1,5], [3], [1,3], [5,3], [1,5,3]]
因为输入的集合的数字都是unique的，这种解法不会产生重复解。
我们可以用下图来可视化这个过程：
代码如下：
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> subsets = new ArrayList<>();
subsets.add(new ArrayList<>());
for(int num : nums) {
int size = subsets.size();
for(int i = 0; i < size; i++) {
List<Integer> set = new ArrayList<>(subsets.get(i));
set.add(num);
subsets.add(new ArrayList<>(set));
}
}
return new ArrayList<>(subsets);
}
}要注意的是，这里如果我们把subsets这个变量定义成Queue的话，也就是LinkedList，在subsets.get(i)这个操作会花费O(n)的时间，而ArrayList的话，subsets.get(i)仅花费O(1)的时间。所以我们可以把subsets定义成ArrayList而不是LinkedList。
时间复杂度：O(N 2 ^ N), N代表set里面存的数字个数，我们一共会有2^N的集合，所以复杂度为O(N 2 ^ N)。 空间复杂度：O(N 2 ^ N)，我们一共有2^N个subset，每一个subset最多可以占用O(N)的空间，所以复杂度为O(N 2 ^ N)。
Follow-up 90. Subsets II
上面这题的input是没有重复数字的，那如果input里含有重复数字了，并且要求outpu不能有重复的subsets，我们应该怎么做呢？
Given an integer array nums that may contain duplicates, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order.
首先比较直接的能想到的是，我们需要把input set给sort一下，这样我们可以保证所有的重复数字都是sit next to each other。
那如果我们碰见了重复数字以后，该怎么办呢？
让我们用 [1, 5, 3, 3] 来举个例子：
- 该数组sort以后，我们得到: [1, 3, 3, 5]
- 先创建一个空集合，加入到我们的队列里: [[]]
- 把第一个数字（1）加到该队列的所有子集合里：[[], [1]]
- 把第二个数字（3）加到该队列的所有子集合里：[[], [1], [3], [1,3]]
- 下一个数字（3）是重复的数字，如果我们把它加到所有的existing subsets里，我们会得到：[[], [1], [3], [1,3], [3], [1,3], [1, 3, 3], [3, 3]]
- 我们发现我们新加的subsets中，[3]和[1,3]是重复的set，我们只需要[1,3,3]和[3,3]。
- 解决的方法很简单，我们只要把这个重复的数字加到上一轮中生成的subsets里就行了：
- 上一轮中生成的subsets是[3], [1,3]，所以加入我们这个重复的3后，这一轮我们新生成[3,3], [1, 3, 3]，再加入到总的集合里就行：[[], [1], [3], [1,3], [3,3], [1, 3, 3]]
下图是以上步骤的可视化操作：
所以我们只需要用两个新的变量，startIndex和endIndex，来控制我们的循环区间就可以了。代码如下：
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> subsets = new ArrayList<>();
if(nums == null || nums.length < 1) return subsets;
Arrays.sort(nums);
subsets.add(new ArrayList<>());
int startIndex = 0, endIndex = 0;
for(int i = 0; i < nums.length; i++) {
startIndex = 0;
// if current and the previous elements are same, create new subsets only from the subsets
// added in the previous step
if(i > 0 && nums[i] == nums[i-1]) {
startIndex = endIndex+1;
}
endIndex = subsets.size()-1;
for(int j = startIndex; j <= endIndex; j++) {
// DO NOT DO: List<Integer> set = subsets.get(j)
// Java is passed by reference and when we modify this set in the following code,
// the set in the result list will also be affected.
List<Integer> set = new ArrayList<>(subsets.get(j));
set.add(nums[i]);
subsets.add(set);
}
}
return subsets;
}
}时间复杂度：O(N * 2 ^ N)*, N代表set里面存的数字个数，我们一共会有2^N的集合，所以复杂度为O(N 2 ^ N)。 空间复杂度：O(N * 2 ^ N)*，我们一共有2^N个subset，每一个subset最多可以占用O(N)的空间，所以复杂度为O(N 2 ^ N)。
78. Subsets 90. Subsets II 46. Permutations 784. Letter Case Permutation 22. Generate Parentheses LintCode. Generalized Abbreviation 320. Generalized Abbreviation 241. Different Ways to Add Parentheses 95. Unique Binary Search Trees II 96. Unique Binary Search Trees
刷题的过程中，我们经常会碰见排列组合的题目。
通常情况下，我们可以用BFS或者backtrack来解决这类问题。