# 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](https://en.wikipedia.org/wiki/Permutation#k-permutations_of_n): 时间和空间都是O(N!).对于第一个位置，有N个选择， 第二个位置有N-1个选择， 到最后一个位置有1个选择， 所以整体是N!

* [Combinations](https://en.wikipedia.org/wiki/Combination#Number_of_k-combinations): $$C\_N^k = \frac{N!}{(N - k)! k!}$$\\

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

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

[ **78. Subsets**](https://leetcode.com/problems/subsets/description/)

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).&#x20;
      * 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的循环结束

```java
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】

```java
    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**](https://leetcode.com/problems/subsets-ii/description/)

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

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