Backtracking - some discussion

Subsets

def subsets(arr: list) -> list:
    n = len(arr)
    def backtrack(idx, comb):
        res.append(comb)
        for i in range(idx, n):
            backtrack(i + 1, comb + [arr[i]])
        
    res = list()
    backtrack(0, [])
    return res

Continuous Subsets

def ctsSubsets(arr: list) -> list:
    n = len(arr)
    def backtrack(idx, comb):
        res.append(comb)
        if idx < n:
            backtrack(idx + 1, comb + [arr[idx]])
        
    res = list()
    for i in range(n):
        backtrack(i+1, [arr[i]])
    return res

How the above two algorithms differ? The “subsets” starts with one single function call, and use a for look inside. While the “contiguous” subsets call the backtrack with for loop outside. The main difference can be outlined by the following graph. In the “subsets” problem, every integer can be combined with a later integer, while the second problem requires that once a start is chosen, all the following numbers has to be added in sequence.

The idx parameter indicates the position of the integer that will be added to the current combination at the next call. So always, when idx==n No new function will be called. Note that this stopping criteria is controlled by the for loop in the “subsets” problem.

Subsets-variation: non-repetitive

A variation of the subsets problem is to narrow the candidates to a sum of a target without repetitious subsets. Though we only need to add two more lines before recursively call the backtrack, the actual considerations can be complex. Consider a list [1,1,6,7], we wants to keep [1,7] for only once, but we want to keep [1,1,6] in the same time, so when the second 1 should be added?

class Solution:
    def combinationSum2(self, candidates, target):
        res = list()
        n = len(candidates)
        def backtrack(idx, comb):
            # meet the target
            if sum(comb) == target:
                res.append(comb)
                return

            # all the numbers have been considered
            if idx == n or sum(comb) > target:
                return
            
            for i in range(idx, n):
                if i > idx and candidates[i] == candidates[i-1]:
                    continue
                backtrack(i + 1, comb + [candidates[i]])

        candidates.sort()
        backtrack(0, [])
        return res

The key is to reduce the same numbers on the same level, which leads to repetitious values, but we do need to include cases where same numbers on different levels. That’s why there is an i>idx in the condition. The below chart shows that we want to get rid of the @2 branch, while keeping the @3.