leetcode - [78] Subsets

2020/02/21

题目描述

Given a set of distinct integers, nums, return all possible subsets (the power set).

给一个不重复的数组,计算出所有可能的子集。

举个例子:

Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

说实话,想了很久,没想到合适的解法,后来参考讨论区,如下:

Update at 2020_0907

重新梳理下两种解法: 递归迭代

递归

关键点在于保存当前字符以及继续遍历后续的字符。

来看下示意图:

再来看下实现:

class Solution {

    List<List<Integer>> ans = new LinkedList<>();

    private void dfs(int[] nums, LinkedList<Integer> child, int u){
        ans.add(new LinkedList<>(child));

        for (int i = u; i < nums.length; i++){
            child.add(nums[i]);
            dfs(nums, child, i + 1);
            child.removeLast();
        }
    }

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

迭代

可以用整数的二进制形式来处理这道题目,举个例子,nums = [1, 2, 3]

正好对应8种结果,其实就是1 ~ 8对应二进制形式中的1,如:

5的二进制形式为(101),对应nums[0] = 1, nums[2] = 3, 也就是[13],其他依次类推:

所以时间复杂度为n*2^n

来看下实现:

class Solution {
    public List<List<Integer>> subsets(int[] nums) {

        List<List<Integer>> ans = new LinkedList<>();
        int n = nums.length;
        for (int i = 0; i < 1 << n; i++){
            var child = new LinkedList<Integer>();
            for (int j = 0; j < n; j++){
                if ((i >> j & 1) == 1){
                    child.add(nums[j]);
                }
            }
            ans.add(new LinkedList<>(child));
        }
        return ans;
    }
}

Update at 2020_0618

此题应该使用回溯思想。

先来看下示意图:

首先,递归方法中我们需要用到哪些东西?

nums原始数组、一个索引值cur、一个临时列表child和一个最终结果列表ans

然后,递归方法中需要做哪些事情?

第一,需要将当前临时列表child加入ans中。

第二,遍历原始数组,记住是从索引值cur开始,并做三件事情:

  • 添加当前元素。
  • 继续递归遍历,注意,索引值cur需要+1
  • 删除当前元素。

来看下实现:

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        
        List<List<Integer>> ans = new LinkedList<>();
        bt(nums, 0, new LinkedList<>(), ans);
        return ans;
    }
    
    private void bt(int[] nums, int cur, LinkedList<Integer> child, List<List<Integer>> ans){
        
        ans.add(new LinkedList<>(child));
        
        for (int i = cur; i < nums.length; i++){
            child.add(nums[i]);
            bt(nums, i + 1, child, ans);
            child.removeLast();
        }
    }
}

解法1

public static List<List<Integer>> p78(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    res.add(new ArrayList<>());
    for (int n: nums){
        int size = res.size();
        for (int i = 0; i < size; i++){
            List<Integer> tmp = new ArrayList<>(res.get(i));
            tmp.add(n);
            res.add(tmp);
        }
    }
    return res;
}

特别是res.get(i)非常惊艳!

Reference


一位喜欢提问、尝试的程序员

(转载本站文章请注明作者和出处 姚屹晨-yaoyichen

Post Directory