Leetcode 78.子集

力扣传送门(opens new window)

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例: 输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

解题思路：

结束条件：

结束条件就是已经遍历完所有的元素，剩余集合为空的时候，就是叶子节点。

那么什么时候剩余集合为空呢？

就是 index 已经等于数组的长度了，就终止了，因为没有元素可取了

具体步骤：

1. 首先，我们创建一个空的结果列表 res来存储所有可能的子集。
2. 然后，我们定义一个辅助函数 backTracking来进行回溯操作。该函数接受三个参数：当前的索引 index，当前的子集 stack，以及原始数组 nums。
3. 在 backTracking函数中，我们首先将当前的子集 stack加入到结果列表 res中，这样就得到了一个新的子集。
4. 接下来，我们从当前的索引 index开始，遍历数组 nums中的元素。
5. 对于每个元素，我们将其加入到子集 stack中，并递归调用 backTracking函数来处理下一个元素。注意，这里的递归调用的索引是 i + 1，表示我们只能选择当前元素之后的元素作为下一个加入的元素，避免重复。
6. 在递归调用返回后，我们将刚刚加入的元素从子集 stack中弹出，以便在下一次循环中构建不同的子集。
7. 最后，当所有的元素都被遍历过后，回溯过程结束，我们就得到了所有可能的子集。

代码实现：

class Solution {
    // 创建一个结果列表来存储所有可能的子集
    List<List<Integer>> res = new ArrayList();  
    public List<List<Integer>> subsets(int[] nums) {  
        // 如果数组为空或长度为0，直接返回结果列表
        if(nums == null || nums.length == 0){  
            return res;
        }
        // 创建一个栈来存储当前的子集
        Stack<Integer> stack = new Stack();  
        // 调用回溯函数生成所有可能的子集
        backTracking(nums, 0, stack);  
        return res;  
    }

    public void backTracking(int[] nums, int index, Stack<Integer> stack) {  
        // 将当前的子集加入结果列表
        res.add(new ArrayList(stack));  
        // 如果已经遍历完所有元素，回溯结束
        if(index == nums.length){  
            return;
        }
        // 遍历数组中剩余的元素
        for(int i = index; i < nums.length; i++){  
            // 将当前元素加入子集
            stack.push(nums[i]);  
            // 递归调用回溯函数处理下一个元素
            backTracking(nums, i + 1, stack);  
            // 回溯，将刚加入的元素弹出，以便构建不同的子集
            stack.pop();  
        }
    }
}