78. Subsets

难度: Medium

题目描述

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

 

Example 1:

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

Example 2:

Input: nums = [0]
Output: [[],[0]]

 

Constraints:

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• All the numbers of nums are unique.

解题思路

代码实现

解决方案

java

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<>());
        List<Integer> current = new ArrayList<>();
        boolean[] added = new boolean[nums.length];

        for (int i = 1; i <= nums.length; i++) {
            backTrack(res, current, i, added, nums,0);
        }
        return res;
    }

    public void backTrack(List<List<Integer>> res, List<Integer> current, int elementCount, boolean[] added,
            int[] nums,int preIndex) {
        if (current.size() == elementCount) {
            res.add(new ArrayList<>(current));
            return;
        }

        for (int i = preIndex; i < nums.length; i++) {
            if (!added[i]) {
                current.add(nums[i]);
                added[i] = true;
                backTrack(res, current, elementCount, added, nums,i+1);
                current.removeLast();
                added[i] = false;
            }
        }

    }
}