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


def permutations(nums):
    res = []
    used = [False] * len(nums)
    path = []
    def bt():
        if len(path) == len(nums):
            res.append(list(path))
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            bt()
            path.pop()
            used[i] = False
    bt()
    return res


def combinations(n, k):
    res = []
    path = []
    def bt(start):
        if len(path) == k:
            res.append(list(path))
            return
        for i in range(start, n + 1):
            path.append(i)
            bt(i + 1)
            path.pop()
    bt(1)
    return res


def combination_sum(candidates, target):
    """Return unique combinations summing to target (candidates reusable).

    Explore candidates in index order; recurse with the same index i so a
    value may repeat, and never revisit earlier indices.
    """
    # TODO: track remaining = target - chosen; record a copy when it hits 0,
    #       prune when it goes below 0.
    pass