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:
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.