题目

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

解答

算法思路

1. 递归决策树：对于数组中的每个元素，都有两种选择：

   • 包含当前元素

   • 不包含当前元素

2. 深度优先搜索：通过递归遍历所有可能的组合

3. 终止条件：当处理完所有元素时（index === nums.length），保存当前子集

var subsets = function(nums) {
    let ans = []; // 存储所有子集结果
    let dfs = (arr, index) => {
        // 递归边界：处理完所有元素
        if (index === nums.length) {
            ans.push([...arr]); // 保存当前子集的副本
            return;
        }
        
        // 选择1：包含当前元素
        dfs([...arr, nums[index]], index + 1);
        
        // 选择2：不包含当前元素
        dfs(arr, index + 1);
    }
    
    dfs([], 0); // 从空数组和索引0开始递归
    return ans;
};