题目描述:
给定一组不含重复元素的整数数组 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);
}
}
}