组合

算法思路：

Leetcode 078的题目。这里作为知识点归纳。

1. 递归中i=st开始。
2. 回溯： path递归后去恢复状态。
3. dfs中传入i+1。
4. 结果要复制new ArrayList<>(path)
5. 一般来说，终止条件才加入结果，但由于子集任何path修改都是子集，所有立即加入。

和全排列的区别：

1. 由于排列可以乱序如[1,2,3]结果是[1,3,2]也就是一个结果需要多次从左向右完全扫描，所以i=0开始且维护visited数组
   组合的结果是按照数组顺序的，所以只要从左到右扫描一次即可，所以用i=st。
2. 结果方面，排列结果是满长度，而组合不是。所以在加入到res位置上，组合用st来判断是否结束且加入到path就立刻进入最后
   结果，而排列是在终结条件上加入。

注意事项：

1. 输入不合法，返回[[]]
2. 记得API是dfs(nums, st, path, result), 4个参数
3. 递归是i+1，不是start+1

学习要点：

详见DFS要点，大部分DFS题目涉及

1. 用到全组合的API: dfs(nums, start, path, result), 4个参数
2. 用到全组合的递归: dfs(nums, i + 1, path, result)
3. 用到全排列的其他部分包括恢复状态和终止条件(加入res)

应用：

1. 找所有可能性

def combine(self, nums: List[int]) -> List[List[int]]:
	if not nums:
		return [[]]
	path, result = [], []
	self.dfs(nums, 0, path, result)
	return result

def dfs(self, nums, st, path, result):
	if len(path) == len(nums):
		return

	for i in range(st, len(nums)):
		path.append(nums[i])
		result.append(list(path))
		self.dfs(nums, i + 1, path, result)
		path.pop()

Java代码：

public List<List<Integer>> subsets(int[] nums) {
	List<Integer> path = new ArrayList<>();
	List<List<Integer>> res = new ArrayList<>();
	res.add(new ArrayList<>(path)); //empty set
	if(nums == null || nums.length == 0)
		return res;
	dfs(nums, 0, path, res);
	return res;
}

void dfs(int[] nums, int st, List<Integer> path, List<List<Integer>> res) {
	if(st == nums.length)
		return;
	
	for(int i = st; i < nums.length; i++) {
		path.add(nums[i]);
		res.add(new ArrayList<>(path));
		dfs(nums, i + 1, path, res);
		path.remove(path.size() - 1);
	}
}

算法分析：

时间复杂度为<code>O(2ⁿ)</code> ，空间复杂度O(1)。