子集

原题链接

使用的方法

回溯

解题思路

• 给定一个整数数组 nums，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。幂集是指一个集合的所有子集，包括空集和集合本身。
• 我们可以使用回溯算法来生成所有可能的子集。回溯算法是一种系统地搜索所有可能的解决方案的方法。在这个问题中，我们可以通过递归地构建子集来生成所有的组合。
• 我们从空集开始，逐步添加数组中的元素来构建子集。在每一步，我们有两个选择：要么包含当前元素，要么不包含当前元素。通过递归地探索这两种选择，我们可以生成所有可能的子集。
• 递归的终止条件是当我们处理到数组的最后一个元素时，我们将当前的子集添加到结果列表中。通过这种方式，我们可以生成所有可能的子集，并最终返回结果列表。

代码实现

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> subsets(int[] nums) {
        dfs(nums,0);
        return res;
    }

    public void dfs(int nums[],int start){
        res.add(new ArrayList<>(path));
        for(int i=start;i<nums.length;i++){
            path.add(nums[i]);
            dfs(nums,i+1);
            path.remove(path.size()-1);
        }
    }
}