core problems►leetcode

LeetCode 78. Subsets

Problem

LeetCode 78. Subsets

1. 题目简述

给出一列不重复整数，找出其所有子集合（包括空集）。例如：

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

2. 算法思路

back tracking回溯法的经典题目之一，和LeetCode 90. Subsets II区别在于，这道题无需考虑重复数字的问题，和combination sum很像。这里是找组合，而不是sum，所以无需排序。

回溯法

直接回溯法计算即可。固定住其中一些位置，然后从前向后找。

时间复杂度：O(n * 2 ^ n)，空间复杂度：O(n)。

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList();
        List<Integer> path = new LinkedList();

        res.add(new ArrayList(path));
        backtracking(nums, 0, path, res);

        return res;
    }

    private void backtracking(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            res.add(new ArrayList(path));
            backtracking(nums, i + 1, path, res);
            path.remove(path.size() - 1);
        }
    }
}