子集

发表于 更新于
本文字数： 1.1k 阅读时长 ≈ 1 分钟

LeetCode每日一题，78. 子集

先看题目描述

大意就是给定一个集合，让我们返回它的所有子集的集合

算法和思路

这题挺简单的，和之前做过的题差不多，使用回溯算法，套公式就可以。需要注意的是，因为返回的解中不能有重复的子集，所以递归时要按照一定顺序，那就是每次往列表中添加元素时只可以添加当前元素下标之后的元素，就这样使用回溯算法就可以解决

算法源码

注意：必须使用 res.add(new ArrayList<>(temp))，而不能使用 res.add(temp)，否则 res 中的每个元素都会变为新的temp 。最终返回的 res 中所有元素为空列表，而不是在 res 的末尾添加新元素 temp，个人认为原因在于 temp 是个引用，当 temp 改变时，res 中所有的元素都是指向 temp 的，于是 res 中的所有元素都随着 temp 的改变而改变，最终 temp 会变为空列表，因为每次都是 res.add(temp)，所以 res 中所有元素都变为空列表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.*;

class Solution {

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(nums, -1, new ArrayList<Integer>(), res);
        return res;
    }

    private void dfs(int[] nums, int index, List<Integer> temp, List<List<Integer>> res) {
        // res.add(temp);
        res.add(new ArrayList<>(temp));
        for (int i = index + 1; i < nums.length; i++) {
            temp.add(nums[i]);
            dfs(nums, i , temp, res);
            temp.remove(Integer.valueOf(nums[i]));
        }
    }
}