关注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 表示不在子集中,那么每一个子集可以对应一个长度为 n0/1 序列,第 i 位表示 a_i 是否在子集中。例如,n = 3a ={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 序列对应的二进制数正好从 02^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

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

12 + 3 =