As a reminder, backtracking is a general algorithm for finding all (or some) solutions to some computational problems. The idea is that it incrementally builds candidates to the solutions, and abandons a candidate (“backtrack”) as soon as it determines that the candidate cannot lead to a final solution.

Imagine the problem as DFS (or BFS) to solve.

Depending upon the problem, it could happen that you need to track

• Approach 1: Backtracking with Counters
• Approach 2: Backtracking with Index

Python template for similar questions:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution(object):
    def combinationSum(self, candidates, target):
        ret = []
        self.dfs(candidates, target, [], ret)
        return ret

    def dfs(self, nums, target, path, ret):
        if target < 0:
            return
        if target == 0:
            ret.append(path)
            return
        for i in range(len(nums)):
            self.dfs(nums[i:], target-nums[i], path+[nums[i]], ret)

Time Complexity 2^n

Worst: In the worst case, our algorithm will exhaust all possible combinations from the input array. Again, in the worst case, let us assume that each number is unique. The number of combination for an array of size NNN would be 2N2^N2N, i.e. each number is either included or excluded in a combination.