39. Combination Sum

The key insight for this problem is understanding how elements can be reused during the search process. When recursively exploring combinations, each element can be selected multiple times since we continue searching from the current index rather than moving to the next one.

Consider the tree structure: after selecting an element, subsequent selections can include that element again or any element that follows it in the sorted array. This prevents duplicate combinations while allowing elements to be reused.

For problems involving a single collection to find combinations, we use startIndex to control which elements are available for selection. For example, LeetCode 77 (Combinations) and 216 (Combination Sum III) follow this pattern. However, when dealing with multiple independent collections where combinations from different sets don't affect eachother, there's no need for startIndex—such as in the Letter Combinations of a Phone Number problem.

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        path = []
        self.backtrack(candidates, 0, target, path, result)
        return result

    def backtrack(self, candidates: List[int], start: int, target: int, path: List[int], result: List[List[int]]) -> None:
        if sum(path) > target:
            return
        if sum(path) == target:
            result.append(path[:])
            return

        for i in range(start, len(candidates)):
            path.append(candidates[i])
            self.backtrack(candidates, i, target, path, result)
            path.pop()

Pruning Optimization

Sorting the candidates array first enables early termination during the search. When the running sum exceeds the target, we can break out of the loop since subsequent elements (in sorted order) will only increase the sum further.

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        path = []
        candidates.sort()
        self.backtrack(candidates, 0, target, path, result)
        return result

    def backtrack(self, candidates: List[int], start: int, target: int, path: List[int], result: List[List[int]]) -> None:
        if sum(path) == target:
            result.append(path[:])
            return

        for i in range(start, len(candidates)):
            if sum(path) > target:
                break
            path.append(candidates[i])
            self.backtrack(candidates, i, target, path, result)
            path.pop()

40. Combination Sum II

This problem differs from the previous one in that each element in the candidates array can only be used once. Additionally, the array may contain duplicate values, requiring careful handling to avoid generating identical combinations.

Handling Duplicates with Sorting

After sorting the candidates, we can skip duplicate elements during the backtracking process. The strategy is: when encountering duplicate values, only proceed with the first occurrence and skip all subsequent identical values at the same recursion level.

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        candidates.sort()
        self.backtrack(candidates, target, 0, 0, [], result)
        return result

    def backtrack(self, candidates: List[int], target: int, total: int, start: int, path: List[int], result: List[List[int]]) -> None:
        if total == target:
            result.append(path[:])
            return

        for i in range(start, len(candidates)):
            if i > start and candidates[i] == candidates[i - 1]:
                continue

            if total + candidates[i] > target:
                break

            total += candidates[i]
            path.append(candidates[i])
            self.backtrack(candidates, target, total, i + 1, path, result)
            total -= candidates[i]
            path.pop()

Handling Duplicates with Used Array

An alternative approach uses a used boolean array to track which elements have been selected in the current path. This approach provides more explicit control over element selection:

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        used = [False] * len(candidates)
        candidates.sort()
        self.backtrack(candidates, target, 0, 0, used, [], result)
        return result

    def backtrack(self, candidates: List[int], target: int, total: int, start: int, used: List[bool], path: List[int], result: List[List[int]]) -> None:
        if total == target:
            result.append(path[:])
            return

        for i in range(start, len(candidates)):
            if i > start and candidates[i] == candidates[i - 1] and not used[i - 1]:
                continue

            if total + candidates[i] > target:
                break

            total += candidates[i]
            path.append(candidates[i])
            used[i] = True
            self.backtrack(candidates, target, total, i + 1, used, path, result)
            used[i] = False
            total -= candidates[i]
            path.pop()

The condition i > start and candidates[i] == candidates[i - 1] and not used[i - 1] ensures that when we encounter a duplicate element, we only proceed with the first occurrence at each recursion level.

131. Palindrome Partitioning

This problem requires finding all ways to partition a string such that each substring is a palindrome. The approach uses backtracking where we extend the partition point incrementally and validate each substring.

The critical insight is that at each recursion level, we iterate from the current start position to the end of the string. For each position, we extract the substring and check if it's a palindrome. Only palindromic substrings are added to the current path before recursing with the next partition point.

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        result = []
        path = []

        def is_palindrome(sub: str) -> bool:
            return sub == sub[::-1]

        def backtrack(start: int) -> None:
            if start >= len(s):
                result.append(path[:])
                return

            for i in range(start, len(s)):
                substring = s[start:i + 1]
                if is_palindrome(substring):
                    path.append(substring)
                    backtrack(i + 1)
                    path.pop()

        backtrack(0)
        return result

The termination condition start >= len(s) triggers when we've processed the entire string, at which point a valid partition has been found. The loop range(start, len(s)) systematically explores all possible partition points, and the palindrome check s[start:i+1] == s[start:i+1][::-1] filters valid substrings using Python's string slicing with step -1.