大家好！我是曾续缘🙃
今天是《LeetCode 热题 100》系列
发车第 56 天
回溯第 2 题
❤️点赞 👍 收藏 ⭐再看，养成习惯

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集不能包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
提示：
1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同
难度：💖💖

解题方法

我们定义一个名为 backtrack 的函数，它接受四个参数：nums 数组、当前位置 cur、临时列表 list 和结果集 ans。

在 backtrack 函数中，我们采用深度优先搜索的思想，不断尝试每一种选择。具体步骤如下：

当前位置 cur 等于数组长度时，表示已经遍历完所有元素，将当前的临时列表 list 加入到结果集 ans 中，并返回，这样就得到了一个子集。
调用回溯函数自身，传入下一个位置 cur+1、当前临时列表 list 和结果集 ans。这表示不选择当前位置的元素，继续递归探索下一个位置的选择。
将当前位置的元素 nums[cur] 加入到临时列表 list 中，表示选择当前位置的元素。
再次调用回溯函数自身，传入下一个位置 cur+1、当前临时列表 list 和结果集 ans。这表示选择当前位置的元素后，继续递归探索下一个位置的选择。
最后，将临时列表 list 中最后一个元素移除，以便继续遍历其他可能的子集。

通过以上的递归回溯过程，我们可以找出给定整数数组的所有可能子集。这是因为在每个位置，我们有两种选择：选择当前位置的元素或者不选择当前位置的元素。通过不断递归调用回溯函数，我们可以遍历所有可能的选择组合，最终得到所有的子集。

回溯算法的核心思想是穷举搜索，通过深度优先遍历的方式，不断尝试每一种选择，直到遍历完所有可能的情况。

Code

查看代码

java

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> list = new ArrayList<Integer>();
        backtrack(nums, 0, list, ans);
        return ans;
    }
    private void backtrack(int[] nums, int cur, List<Integer>list, List<List<Integer>> ans){
        if(cur == nums.length){
            ans.add(new ArrayList<Integer>(list));
            return;
        }
        backtrack(nums, cur + 1, list, ans);
        list.add(nums[cur]);
        backtrack(nums, cur + 1, list, ans);
        list.remove(list.size() - 1);
    }
}

解题方法 ​

Code ​

解题方法

Code