关注Java领域相关技术 记录有趣的事情

LeetCode-78. 子集

US-B.Ralph
US-B.Ralph
2020-09-20

问题地址

LeetCode每日一题/2020-09-20

LeetCode78. 子集

问题描述

规则

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

说明

  • 解集不能包含重复的子集。

示例

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

解析

解题思路

  • 每个元素都有两个选项，选择、不选择；
    • 题目示例[1，2，3]，元素1可以考虑选择或不选择，然后考察2，以此类推；
    • 其递归树为：
  • 一个子树就是一个递归调用，对当前枚举的数，选和不选可以分出两个分支，分别对应两个递归的子调用，在子调用中，考察下一个数。
  • 当 inx 越界（inx == nums.length）时，就把生成的子集加入解中，结束当前递归分支。
  • 我们找到一个子集结束递归，要撤销当前的选择（把当前选的数从 list 中删掉），回到选择前的状态，做另一个选择——不选当前的数，往下递归，继续生成子集。

数据操作分析

  • 判断当前指针是否等于给定序列的长度，若 inx == nums.length 则将当前子集假如到解中，并结束当前递归；
  • 若 inx 则将当前元素加入到当前子集中，并继续下一个数选择；
  • 回溯，撤销当前的选择回到选择前的状态，不选当前数继续往下递归；

复杂度分析

  1. 时间复杂度
  2. 空间复杂度

编码实现

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

    private void dfs(List<List<Integer>> ans, List<Integer> tmp, int inx, int[] nums) {
        if (inx == nums.length) {
            ans.add(new ArrayList<>(tmp));
            return;
        }
        tmp.add(nums[inx]);
        dfs(ans, tmp, inx + 1, nums);
        tmp.remove(tmp.size() - 1);
        dfs(ans, tmp, inx + 1, nums);
    }
}

官方解法

方法一：迭代法实现子集枚举

思路：

  • 记原序列中元素的总数为 n。原序列中的每个数字 a_i 的状态可能有两种，即「在子集中」和「不在子集中」。我们用 1 表示「在子集中」，0 表示不在子集中，那么每一个子集可以对应一个长度为 n 的 0/1 序列，第 i 位表示 a_i 是否在子集中。例如，n = 3 ，a ={5, 2, 9 } 时：

    0/1 序列 子集 0/1 序列对应的二进制数
    000 {} 0
    001 {9} 1
    010 {2} 2
    011 {2,9} 3
    100 {5} 4
    101 {5,9} 5
    110 {5,2} 6
    111 {5,2,9} 7

  • 可以发现 0/1 序列对应的二进制数正好从 0 到 2^n – 1。我们可以枚举 {\rm mask} \in [0, 2^n – 1]，\rm mask 的二进制表示是一个 0/1 序列，我们可以按照这个 0/1 序列在原集合当中取数。当我们枚举完所有 2^n 个 \rm mask，我们也就能构造出所有的子集。

复杂度分析：

  1. 时间复杂度:O(n×2^n )。一共 2^n 个状态，每种状态需要 O(n) 的时间来构造子集。
  2. 空间复杂度：O(n)。即构造子集使用的临时数组 t 的空间代价。

编码实现

class Solution {
    List<Integer> t = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        for (int mask = 0; mask < (1 << n); ++mask) {
            t.clear();
            for (int i = 0; i < n; ++i) {
                if ((mask & (1 << i)) != 0) {
                    t.add(nums[i]);
                }
            }
            ans.add(new ArrayList<Integer>(t));
        }
        return ans;
    }
}

方法一：递归法实现子集枚举

思路：

  • 我们也可以用递归来实现子集枚举。假设我们需要找到一个长度为 nn 的序列 aa 的所有子序列，代码框架是这样的：
vector<int> t;
void dfs(int cur, int n) {
    if (cur == n) {
        // 记录答案
        // ...
        return;
    }
    // 考虑选择当前位置
    t.push_back(cur);
    dfs(cur + 1, n, k);
    t.pop_back();
    // 考虑不选择当前位置
    dfs(cur + 1, n, k);
}
  • 上面的代码中，{\rm dfs(cur,} n) 参数表示当前位置是 \rm cur，原序列总长度为 n。原序列的每个位置在答案序列中的状态有被选中和不被选中两种，我们用 \rm t 数组存放已经被选出的数字。在进入 {\rm dfs(cur,} n) 之前 \rm [0, cur – 1] 位置的状态是确定的，而 [{\rm cur}, n – 1] 内位置的状态是不确定的，{\rm dfs(cur,} n) 需要确定 \rm cur 位置的状态，然后求解子问题 {\rm dfs(cur + 1}, n)。对于 \rm cur 位置，我们需要考虑 a[{\rm cur}] 取或者不取，如果取，我们需要把 a[{\rm cur}] 放入一个临时的答案数组中（即上面代码中的 \rm t），再执行 {\rm dfs(cur + 1}, n)，执行结束后需要对 \rm t 进行回溯；如果不取，则直接执行 {\rm dfs(cur + 1}, n)。在整个递归调用的过程中，\rm cur 是从小到大递增的，当 \rm cur 增加到 n 的时候，记录答案并终止递归。可以看出二进制枚举的时间复杂度是 O(2^n)。

复杂度分析：

  1. 时间复杂度:O(n×2^n )。一共 2^n 个状态，每种状态需要 O(n) 的时间来构造子集。
  2. 空间复杂度：O(n)。临时数组 t 的空间代价是 O(n)，递归时栈空间的代价为 O(n)。

编码实现

class Solution {
    List<Integer> t = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

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

    public void dfs(int cur, int[] nums) {
        if (cur == nums.length) {
            ans.add(new ArrayList<Integer>(t));
            return;
        }
        t.add(nums[cur]);
        dfs(cur + 1, nums);
        t.remove(t.size() - 1);
        dfs(cur + 1, nums);
    }
}

精彩评论

跳转地址1：二进制位，逐个枚举，DFS 三种思路，9+ 种以上的写法

思路一：

  • 集合的每个元素，都有可以选或不选，用二进制和位运算，可以很好的表示。

编码实现

    public static List<List<Integer>> binaryBit(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        for (int i = 0; i < (1 << nums.length); i++) {
            List<Integer> sub = new ArrayList<Integer>();
            for (int j = 0; j < nums.length; j++)
                if (((i >> j) & 1) == 1) sub.add(nums[j]);
            res.add(sub);
        }
        return res;
    }

思路二：

  • 逐个枚举，空集的幂集只有空集，每增加一个元素，让之前幂集中的每个集合，追加这个元素，就是新增的子集。

编码实现

    /**
     * 循环枚举
     */
    public static List<List<Integer>> enumerate(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        res.add(new ArrayList<Integer>());
        for (Integer n : nums) {
            int size = res.size();
            for (int i = 0; i < size; i++) {
                List<Integer> newSub = new ArrayList<Integer>(res.get(i));
                newSub.add(n);
                res.add(newSub);
            }
        }
        return res;
    }

    /**
     * 递归枚举
     */
    public static void recursion(int[] nums, int i, List<List<Integer>> res) {
        if (i >= nums.length) return;
        int size = res.size();
        for (int j = 0; j < size; j++) {
            List<Integer> newSub = new ArrayList<Integer>(res.get(j));
            newSub.add(nums[i]);
            res.add(newSub);
        }
        recursion(nums, i + 1, res);
    }

思路三：

  • 集合中每个元素的选和不选，构成了一个满二叉状态树，比如，左子树是不选，右子树是选，从根节点、到叶子节点的所有路径，构成了所有子集。可以有前序、中序、后序的不同写法，结果的顺序不一样。本质上，其实是比较完整的中序遍历。

编码实现

    /**
     * DFS，前序遍历
     */
    public static void preOrder(int[] nums, int i, ArrayList<Integer> subset, List<List<Integer>> res) {
        if (i >= nums.length) return;
        // 到了新的状态，记录新的路径，要重新拷贝一份
        subset = new ArrayList<Integer>(subset);

        // 这里
        res.add(subset);
        preOrder(nums, i + 1, subset, res);
        subset.add(nums[i]);
        preOrder(nums, i + 1, subset, res);
    }

    /**
     * DFS，中序遍历
     */
    public static void inOrder(int[] nums, int i, ArrayList<Integer> subset, List<List<Integer>> res) {
        if (i >= nums.length) return;
        subset = new ArrayList<Integer>(subset);

        inOrder(nums, i + 1, subset, res);
        subset.add(nums[i]);
        // 这里
        res.add(subset);
        inOrder(nums, i + 1, subset, res);
    }

    /**
     * DFS，后序遍历
     */
    public static void postOrder(int[] nums, int i, ArrayList<Integer> subset, List<List<Integer>> res) {
        if (i >= nums.length) return;
        subset = new ArrayList<Integer>(subset);

        postOrder(nums, i + 1, subset, res);
        subset.add(nums[i]);
        postOrder(nums, i + 1, subset, res);
        // 这里
        res.add(subset);
    }
  • 也可以左子树是选，右子树是不选，相当于，也可以前序、中序、后序的不同写法。程序实现上，需要用一个栈，元素入栈遍历左子树，（最近入栈的那个）元素出栈，遍历右子树。
    public static void newPreOrder(int[] nums, int i, LinkedList<Integer> stack, List<List<Integer>> res) {
        if (i >= nums.length) return;
        stack.push(nums[i]);
        // 这里
        res.add(new ArrayList<Integer>(stack));
        newPreOrder(nums, i + 1, stack, res);
        stack.pop();
        newPreOrder(nums, i + 1, stack, res);
    }
  • 还有一种是回溯的写法，仍然是那颗状态树，不过不再走遍所有的节点，而是通过回溯，跳过一些节点。前面那种标准的二叉树中序遍历，虽然更容易理解，其实实用性有限，非常不利于剪枝。
    public static void backtrack(int[] nums, int i, List<Integer> sub, List<List<Integer>> res) {
        for (int j = i; j < nums.length; j++) {
            if (j > i && nums[j] == nums[j - 1]) continue;
            sub.add(nums[j]);
            res.add(new ArrayList<Integer>(sub));
            backtrack(nums, j + 1, sub, res);
            sub.remove(sub.size() - 1);
        }
    }

跳转地址2：78. 子集:【回溯搜索法】经典题目详解！

思路

  • 求子集问题和 求组合组合和分割问题又不一样了， 如何把 子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是找树的叶子节点，而子集问题是找树的所有节点！取子集也是，其实也是一种组合位置，因为它的集合是无序的，子集{1,2} 和 子集{2,1}是一样的。 那么既然是无序，写回溯算法的时候，for就要从startIndex开始，而不是从0开始！那有同学问题，什么时候，for可以从0开始，求排列问题的时候，就要从0开始，因为集合是有序的，{1, 2} 和{2, 1}是两个集合。以示例中nums = [1,2,3]为例把求子集抽象为树型结构，如下：
  • 从图中，可以看出，遍历这个树的时候，把所有节点都记录下来，就是要求的子集。来看一下我总结的回溯模板来：
backtracking() {
    if (终止条件) {
        存放结果;
    }

    for (选择：选择列表（可以想成树中节点孩子的数量）) {
        递归，处理节点;
        backtracking();
        回溯，撤销处理结果
    }
}
  • 首先是终止条件，终止条件，就是startIndex已经大于数组的长度了，就是终止了，代码如下:
if (startIndex >= nums.size()) {
    return;
}
  • 但是，要明确的是，求取子集问题，其实没有必要加终止条件，因为子集就是要遍历整个一棵树，不需要任何剪枝！大家一会看到下面整体代码的时候就知道了。
  • 然后就是看如何写for循环，因为求子集也是无序的，所以for循环要从startIndex开始！ 代码如下：
for (int i = startIndex; i < nums.size(); i++) {}
  • 接下来就是递归与回溯，定一个vector path，用来收集子集的元素，在回溯的时候还要弹出，backtracking每次调用自己的时候，记着要从i+1 开始，代码如下：
for (int i = startIndex; i < nums.size(); i++) {
    path.push_back(nums[i]);
    backtracking(nums, i + 1);
    path.pop_back();
}
  • 重点代码分析完之后，整体代码如下：
    • 可以发现我在backtracking里并没有写终止条件，因为本来我们就要遍历整颗树。
  • 有的同学可能担心会不会无限递归？ 并不会，因为每次递归的下一层就是从i+1开始的。

编码实现

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums, int startIndex) {
        result.push_back(path);
        for (int i = startIndex; i < nums.size(); i++) {
            path.push_back(nums[i]);
            backtracking(nums, i + 1);
            path.pop_back();
        }
    }
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        result.clear();
        path.clear();
        backtracking(nums, 0);
        return result;
    }
};

跳转地址3：回溯算法

思路一:库函数

编码实现

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        for i in range(len(nums)+1):
            for tmp in itertools.combinations(nums, i):
                res.append(tmp)
        return res

思路二:迭代

编码实现

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = [[]]
        for i in nums:
            res = res + [[i] + num for num in res]
        return res

思路三:递归(回溯算法)

编码实现

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

    }

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

类似题目

//78子集
class Solution:
    def subsets(self, nums):        
                if not nums:
            return []
        res = []
        n = len(nums)

        def helper(idx, temp_list):
            res.append(temp_list)
            for i in range(idx, n):
                helper(i + 1, temp_list + [nums[i]])

        helper(0, [])
        return res

//90. 子集 II
class Solution(object):
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if not nums:
            return []
        n = len(nums)
        res = []
        nums.sort()
        # 思路1
        def helper1(idx, n, temp_list):
            if temp_list not in res:
                res.append(temp_list)
            for i in range(idx, n):
                helper1(i + 1, n, temp_list + [nums[i]])
        # 思路2
        def helper2(idx, n, temp_list):
            res.append(temp_list)
            for i in range(idx, n):
                if i > idx and  nums[i] == nums[i - 1]:
                    continue
                helper2(i + 1, n, temp_list + [nums[i]])

        helper2(0, n, [])
        return res

//46. 全排列
class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if not nums:
            return
        res = []
        n = len(nums)
        visited = [0] * n
        def helper1(temp_list,length):
            if length == n:
                res.append(temp_list)
            for i in range(n):
                if visited[i] :
                    continue
                visited[i] = 1
                helper1(temp_list+[nums[i]],length+1)
                visited[i] = 0
        def helper2(nums,temp_list,length):
            if length == n:
                res.append(temp_list)
            for i in range(len(nums)):
                helper2(nums[:i]+nums[i+1:],temp_list+[nums[i]],length+1)
        helper1([],0)
        return res

//47. 全排列 II
class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
                if not nums:
            return []
        nums.sort()
        n = len(nums)
        visited = [0] * n
        res = []

        def helper1(temp_list, length):
            # if length == n and temp_list not in res:
            #   res.append(temp_list)
            if length == n:
                res.append(temp_list)
            for i in range(n):
                if visited[i] or (i > 0 and nums[i] == nums[i - 1] and not visited[i - 1]):
                    continue
                visited[i] = 1
                helper1(temp_list + [nums[i]], length + 1)
                visited[i] = 0

        def helper2(nums, temp_list, length):
            if length == n and temp_list not in res:
                res.append(temp_list)
            for i in range(len(nums)):
                helper2(nums[:i] + nums[i + 1:], temp_list + [nums[i]], length + 1)

        helper1([],0)
        # helper2(nums, [], 0)
        return res

//39.组合总和
class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        if not candidates:
            return []
        if min(candidates) > target:
            return []
        candidates.sort()
        res = []

        def helper(candidates, target, temp_list):
            if target == 0:
                res.append(temp_list)
            if target < 0:
                return
            for i in range(len(candidates)):
                if candidates[i] > target:
                    break
                helper(candidates[i:], target - candidates[i], temp_list + [candidates[i]])
        helper(candidates,target,[])
        return res

//40. 组合总和 II
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        if not candidates:
            return []
        candidates.sort()
        n = len(candidates)
        res = []

        def backtrack(i, tmp_sum, tmp_list):
            if tmp_sum == target:
                res.append(tmp_list)
                return 
            for j in range(i, n):
                if tmp_sum + candidates[j]  > target : break
                if j > i and candidates[j] == candidates[j-1]:continue
                backtrack(j + 1, tmp_sum + candidates[j], tmp_list + [candidates[j]])
        backtrack(0, 0, [])    
        return res
US-B.Ralph
LeetCode数据结构与算法算法

Leave a Comment

邮箱地址不会被公开。 必填项已用*标注

4 × 1 =