【Leetcode 78】子集 —— 回溯法

78. 子集

给你一个整数数组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. 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索

回溯法有“通用解题法”之称，用它可以系统地搜索问题的所有解。回溯法是一个既带有系统性又带有跳跃性的搜索算法。
详细可见 Leetcode 回溯法详解

经典排列树，按节点遍历，更多案例可见 Leetcode 回溯法详解

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

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