Leetcode78子集

此题除了二进制迭代来做，同样也可以用回溯来做

递归函数作用：从传入的下标处开始，依次处理当前以及后面的元素，每个元素可选可不选，收集所有可能的子集。

回溯状态：t集合

递归出口：所有结点都处理完成，收集所有可能的子集。

第一步：将当前元素加入t集合

第二步：递归处理下一个元素，此时直到递归至出口，都是包含当前元素的

第三步：从t集合中移除当前元素

第四步：递归处理下一个元素，此时直到递归至出口，都是不包含当前元素的

class Solution { List<Integer> t = new ArrayList<Integer>(); List<List<Integer>> ans = new ArrayList<List<Integer>>(); public List<List<Integer>> subsets(int[] nums) { dfs(0, nums); return ans; } public void dfs(int cur, int[] nums) { if (cur == nums.length) { ans.add(new ArrayList<Integer>(t)); return; } t.add(nums[cur]); dfs(cur + 1, nums); t.remove(t.size() - 1); dfs(cur + 1, nums); } }