LintCode 17. 子集 JavaScript算法

描述

给定一个含不同整数的集合，返回其所有的子集。

说明

子集中的元素排列必须是非降序的，解集必须不包含重复的子集。

样例

- 样例 1：

输入：[0]
输出：
[
  [],
  [0]
]

- 样例 2：

输入：[1,2,3]
输出：
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

挑战

你可以同时用递归与非递归的方式解决么？

解析

这里LintCode平台有bug，有一组数据测试不通过，所以我是用Java提交的

subsets = function (nums) {
    if(nums.length===0) return [[]]
    let result = []
    nums.sort((a, b) => a-b).forEach(item => {
        result.forEach(r => { result.push([...r, item]) })
        if(result.length===0){
            result.push([])
            result.push([item])
        }
    })
    return result
}

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        Deque<Integer> subset = new ArrayDeque<>(nums.length);
        dfs(nums, 0, subset, res);
        return res;
    }
    private void dfs(int[] nums, int k, Deque<Integer> subset, List<List<Integer>> res) {
        res.add(new ArrayList<>(subset));
        for (int i = k; i < nums.length; ++i) {
            subset.addLast(nums[i]);
            dfs(nums, i + 1, subset, res);
            subset.removeLast();
        }
    }
}

运行结果