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!

• Combinations: $C_N^k = \frac{N!}{(N - k)! k!}$

• Subsets: $2^N$, since each element could be absent or present.

这类问题的基础模版是subset.

78. Subsets

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

90. Subsets II

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);
        }
    }
}