MediumLeetCode #78Backtracking

Subsets

Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets.

Constraints

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

Examples

Input: nums = [1,2,3]

Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Solution

Approach

Backtracking: at each index, choose to include or exclude the element. Alternatively, iterate and double subsets at each step.

def subsets(nums):
    result = []
    def backtrack(start, path):
        result.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    backtrack(0, [])
    return result

Complexity

Time:O(n * 2^n)

Space:O(n)

Hints

1.Think about include/exclude decision for each element
2.Backtracking explores all combinations
3.Can also use bit manipulation

Asked at

Google