Subset (子集，BackTracking 模版）
Permutations / Combinations / Subsets, since they are quite similar to each other and there are some common strategies to solve them.
Their solution space is often quite large:
Permutations: 时间和空间都是O(N!).对于第一个位置，有N个选择， 第二个位置有N-1个选择， 到最后一个位置有1个选择， 所以整体是N!
Subsets: , since each element could be absent or present.
这类问题的基础模版是subset.
Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]My Solutions:
方法1:
递归。注意function backtrack的for loop中，i=start，在iterate int[]nums 的时候，从前往后找
e.g. 【1，2，3】
第一次进入backtrack，list里加入空集[]；
list里有[], 进入for loop: start = 0, i=0, temp=[1], backtrack(list, temp, nums, 1)
list里有[], [1]; start = 1, i = 1, temp=[1,2], backtrack(list, temp, nums, 2)
list里有[], [1], [1,2]; start = 2, i = 2, temp=[1,2,3], backtrack(list, temp, nums, 3).
list里有[], [1], [1,2], [1,2,3]; start = 3不再进入for loop，返回到上一层
list里有[], [1], [1,2], [1,2,3]; start = 2, i = 2, temp=[1,2,3]. 去掉temp里最后的元素, temp=[1,2]，返回到上一层
list里有[], [1], [1,2], [1,2,3]; start = 1; i = 1, temp=[1,2]. 去掉temp里最后的元素, temp=[1]，返回到上一层
list里有[], [1], [1,2], [1,2,3]; start = 0; i = 0, temp=[1]. 去掉temp里最后的元素, temp=[]，返回到上一层
此时回到start = 0 for loop的开头，i = 1, 进入for loop的第二次循环:
list里有[], [1], [1,2], [1,2,3]; start = 0, i = 1, temp=[2], backtrack(list, temp, nums, 2]
list里有[], [1], [1,2], [1,2,3], [2]; start = 2, i = 2, temp=[2,3], backtrack(list, temp, nums, 3]
list里有[], [1], [1,2], [1,2,3], [2],[2,3]; start = 3不再进入for loop，返回到上一层
list里有[], [1], [1,2], [1,2,3], [2], [2,3]; start = 2, i = 2, temp=[2,3]. 去掉temp里最后的元素, temp=[2]，返回到上一层
list里有[], [1], [1,2], [1,2,3], [2], [2,3]; start = 0, i = 1, temp=[2]. 去掉temp里最后的元素, temp=[]，返回到上一层
此时回到start = 0 for loop的开头，i = 2, 进入for loop的第三次循环:
list里有[], [1], [1,2], [1,2,3], [2], [2,3]; start = 0, i = 2, temp=[3]. backtrack(list, temp, nums, 3]
list里有[], [1], [1,2], [1,2,3], [2], [2,3],[3]. start=3不再进入for loop，返回到上一层
for loop的循环结束
class Solution {
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> temp, int[] nums, int start) {
list.add(new ArrayList<>(temp)); //往最终结果中先放入之前的temp
for (int i = start; i < nums.length; i++) {
temp.add(nums[i]); //往之前的temp放入新元素
backtrack(list, temp, nums, i + 1); //注意这里是i + 1
temp.remove(temp.size() - 1); //回到这里的时候，需要去掉temp里最后加入的元素
}
}
}Time: O(N * (2^N)), generate all subsets and then copy them into output list.
Space: O(N)
方法2：
按照组合的思想，一个数字都没有的时候是空集；有一个数字，则这个数字+空集是一个新集合。因此，每循环到一个新元素，就把之前已经加入的所有list的所有【】再加上这个元素，再加入最终结果的list
e.g. 【1，2，3】
一开始list里只有空集【】；
nums中第一个n是1，n=1，list.size=1，
inner for loop循环一次之后list是【】，【1】
num中第二个n是2，n=2, list.size=2,
inner for loop循环一次之后list是【】，【1】，【2】
inner for loop循环二次之后list是【】，【1】，【2】，【1，2】
nums中第三个n是3，n=3，size=4，
inner for loop循环一次结束后，list是【】，【1】，【2】，【1，2】，【3】；
inner for loop循环第二次后list是【】，【1】，【2】，【1，2】，【3】，【1，3】；
第三次后是【】，【1】，【2】，【1，2】，【3】，【1，3】，【2，3】；
第四次后是【】，【1】，【2】，【1，2】，【3】，【1，3】，【2，3】，【1，2，3】
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
list.add(new ArrayList<>()); //空集
for (int n : nums) { //从nums中取出每一个元素
int size = list.size();
for (int i = 0; i < size; i++) {
List<Integer> temp = new ArrayList<>(list.get(i)); //temp是list中已有的数组
temp.add(n); //把新元素加入temp
list.add(temp); //新temp加入list中
}
}
return list;
}Time: O(N * (2^N)), generate all subsets and then copy them into output list.
Space: O(N * (2^N)), number of solutions for subsets multiplied by the number N of elements to keep for each subset
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:
Input: [1,2,2]
Output:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]My Solutions:
和上题类似，多增加一步跳过duplicates
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums); // sort之后保证未来可以跳过重复数字
dfs(list, new ArrayList<>(), nums, 0);
return list;
}
public void dfs(List<List<Integer>> list, List<Integer> temp, int[] nums, int start) {
list.add(new ArrayList<>(temp));
for (int i = start; i < nums.length; i++) {
if (i > start && nums[i] == nums[i - 1]) continue; //跳过duplicates
temp.add(nums[i]);
dfs(list, temp, nums, i + 1);
temp.remove(temp.size() - 1);
}
}
}Last updated