题目描述
给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的> > 子集(幂集)。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
解题思路
采用回溯算法暴力求解
回溯算法模板
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
代码
static List<List<Integer>> res = new LinkedList<>();
static List<List<Integer>> subsets(int[] nums) {
LinkedList<Integer> track = new LinkedList<>();
backtrack(nums, track, 0);
return res;
}
static void backtrack(int[] nums, LinkedList<Integer> track, int start) {
res.add(new LinkedList(track));
for (int i = start; i < nums.length; i++) {
if (track.contains(nums[i])) {
continue;
}
track.add(nums[i]);
// 进入下一层决策树
backtrack(nums, track, i + 1);
// 取消选择
track.removeLast();
}
}
Q.E.D.