【Leecode】Leecode刷题之路第78天之子集

Scroll Down

题目出处

78-子集-题目出处

题目描述

78-子集-题目描述

个人解法

思路:

todo

代码示例:(Java)

todo

复杂度分析

todo

官方解法

78-子集-官方解法

方法1:迭代法实现子集枚举

思路:

78-子集-迭代法实现子集枚举-思路

代码示例:(Java)

public class Solution1 {
    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;
    }


}

复杂度分析

78-子集-迭代法实现子集枚举-复杂度分析

方法2:递归法实现子集枚举

思路:

78-子集-递归法实现子集枚举-思路

代码示例:(Java)

public class Solution2 {
    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);
    }


}

复杂度分析

78-子集-递归法实现子集枚举-复杂度分析

考察知识点

收获

Gitee源码位置

78-子集-源码

同名文章,已同步发表于CSDN,个人网站,公众号