Backtracking

Sum of All Subset XOR Totals

Find the sum of the XOR total of every subset of nums, subsets with the same elements counted once per distinct subset. nums = [1,3] → subsets [], [1], [3], [1,3] → XOR totals 0, 1, 3, 2 → sum 6.

DFS: include or exclude each number

• dfs(i, total), i is the current index, total is the running XOR of everything included so far.
• Base case: i == len(nums), one full subset decided, return total.
• Recursive case: branch into two calls, one including nums[i] (XOR it into total), one excluding it, sum both branches' results.
• Every root-to-leaf path is one subset, so the sum returned at the root is the sum over all 2^n subsets.

class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
 
        def dfs(i, total):
            if i == len(nums):
                return total
 
            return dfs(i + 1, total ^ nums[i]) + dfs(i + 1, total)
 
        return dfs(0, 0)

Subsets

Return all possible subsets of nums (the power set), no duplicates in the input. nums = [1,2,3] → [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]].

1. Include, then exclude

• subset is the current partial subset being built, shared across the whole recursion via append/pop.
• dfs(i), base case i >= len(nums), the subset is complete, append a copy of it to res and return.
• Decision to include nums[i]: append it to subset, recurse to i+1.
• Decision to exclude nums[i]: pop it back off subset, recurse to i+1 again, same branching shape as Sum of All Subset XOR Totals above, just building an actual list instead of a running XOR.

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
 
        subset = []
 
        def dfs(i):
            if i >= len(nums):
                res.append(subset.copy())
                return
 
            # decision to include nums[i]
            subset.append(nums[i])
            dfs(i + 1)
 
            # decision NOT to include nums[i]
            subset.pop()
            dfs(i + 1)
 
        dfs(0)
        return res

2. Exclude, then include

• Same two branches as above, just flipped: recurse without nums[i] first, then append it, recurse again, and pop it back off.
• Order of the two recursive calls doesn't change which subsets get found, only the order res ends up in, backtrack(i+1) before touching sol still visits every include/exclude combination exactly once.
• sol[:] is a slice-copy, does the same job as subset.copy() above, just different syntax for the same "snapshot the list before it keeps mutating" need.

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        res, sol = [], []
 
        def backtrack(i):
            if i == n:
                res.append(sol[:])
                return
 
            # Don't pick nums[i]
            backtrack(i + 1)
 
            # Pick nums[i]
            sol.append(nums[i])
            backtrack(i + 1)
            sol.pop()
 
        backtrack(0)
        return res