Loading...
墨滴

SuperMP

2021/04/20  阅读:92  主题:默认主题

Leetcode刷题 | 第113题:子集

孤独的人不会伤害别人,只会不断地伤害自己罢了。

78. 子集[1]

题目:给你一个整数数组 nums ,数组中的元素互不相同。返回该数组所有可能的子集(幂集)。解集不能包含重复的子集。你可以按任意顺序返回解集。

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

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

提示:
1 <= nums.length <= 10, -10 <= nums[i] <= 10
nums 中的所有元素 互不相同

分析:回溯。对于长度为 n 的数组,每一个位置都有两种可能:选 / 不选。因此,对于数组中的每一个 index 位置,都可以进行(选 / 不选)的选择,然后递归地对第 index + 1 个元素进行选择,直到对数组的最后一个元素选择完毕,即可构成一个子集(递归中不同的选择构成了不同的子集)。

假设 n = 3,0 表示不选,1 表示选择,对于 0, 1, 2 索引对应的可选方案为:000, 001, 010, 011, 100, 101, 110, 111,共 个子集。

Java代码:

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

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

    public void backtrack(int[] nums, int idx) {
        if (idx == nums.length) {
            ans.add(new ArrayList<>(temp));
            return;
        }
        temp.add(nums[idx]); // 选当前 idx 处的元素
        backtrack(nums, idx + 1);
        temp.remove(temp.size() - 1); // 回溯
        
        backtrack(nums, idx + 1); // 不选当前 idx 处的元素
    }
}
  • 时间复杂度为 O(N * 2^N),一共有 2^N 个子集状态,且构造每一个子集状态都需要 O(N) 的时间;空间复杂度为 O(N)。

QUESTION:若数组中存在重复元素,如何构造出不包含重复子集的集合呢?(明天学习)

参考资料

[1]

子集: https://leetcode-cn.com/problems/subsets/

SuperMP

2021/04/20  阅读:92  主题:默认主题

作者介绍

SuperMP