题目描述：
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例: 输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
题目解析：回溯的过程是执行一次深度优先遍历，一条路走到底，走不通的时候，返回回来，继续执行，一直这样下去，直到回到起点。
代码实现：注意空集也是集合的子集
将结果集扩大操作放在循环里面
public static List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
return backTrace(0, nums, res, new ArrayList<>());
}
private static List<List<Integer>> backTrace(int i, int[] nums, List<List<Integer>> res, ArrayList<Integer> tmp) {
if (tmp.size() == 0) {
res.add(new ArrayList<>(tmp));
}
for (int j = i; j < nums.length; j++) {
tmp.add(nums[j]);
res.add(new ArrayList<>(tmp));
backTrace(j + 1, nums, res, tmp);
//递归结束，恢复状态
tmp.remove(tmp.size() - 1);
}
return res;
}
将结果集新增放在循环外面
class Solution {
public static List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
backtrack(0, nums, res, new ArrayList<>());
return res;
}
private static void backtrack(int i, int[] nums, List<List<Integer>> res, ArrayList<Integer> tmp) {
res.add(new ArrayList<>(tmp));
for (int j = i; j < nums.length; j++) {
tmp.add(nums[j]);
backtrack(j + 1, nums, res, tmp);
tmp.remove(tmp.size() - 1);
}
}
}
