Subsets

A subset (also called the power set when you list all of them) is any selection of elements where order does not matter: {1, 3} and {3, 1} are the same subset. A set of n elements has 2^n subsets, including the empty set and the full set.

The backtracking version uses a start index: at each call you may add any element at or after start, then recurse with the next index. Because you only look to the right, each subset is produced exactly once, in one fixed order.

When the input has duplicate values, like [1, 2, 2], you sort first and skip a value if it equals the previous value at the same level of the tree, so {1, 2} is not produced twice.

1. 1Keep one list path for the current subset and one list result.
2. 2On every call, first record a copy of path: every node in the tree is a valid subset, not just the leaves.
3. 3Loop i from start to n - 1: add nums[i], recurse with start = i + 1, then remove nums[i].
4. 4Because the next call starts at i + 1, an element can never be picked twice and the order inside a subset always follows the input order, so no subset repeats.
5. 5For inputs with duplicates, sort, and inside the loop skip i when i > start and nums[i] == nums[i - 1].

def subsets(nums):
    result, path = [], []

    def backtrack(start):
        result.append(path[:])          # every node is a subset
        for i in range(start, len(nums)):
            path.append(nums[i])        # choose nums[i]
            backtrack(i + 1)            # only look to the right
            path.pop()                  # un-choose

    backtrack(0)
    return result

def subsets_with_dup(nums):
    nums = sorted(nums)
    result, path = [], []

    def backtrack(start):
        result.append(path[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue                # same value at same level: skip
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()

    backtrack(0)
    return result

Both functions record path at every call. The second sorts the input and skips a value that equals its left neighbour at the same level, so for [1, 2, 2] it returns [], [1], [1, 2], [1, 2, 2], [2], [2, 2] with no repeats.

Cost: There are 2^n subsets and copying each costs up to O(n), so time is O(n * 2^n). Extra space is O(n) for the path and recursion, plus O(n * 2^n) for the output.