Combination Sum

The objective is to find all unique combinations from a list of candidate numbers that sum up to a given target. Each number may be used multiple times.

The solution uses recursive backtracking with the following approach:

• Parameters include the candidate array, target value, current combination, and results collection
• Termination occurss when the current sum exceeds the target, or equals it (at which point the combination is stored)
• During iteration, elements are selected starting from the current position to avoid duplicate combinations

class Solution:
    def explore_combinations(self, options, goal, current_path, outcomes):
        path_sum = sum(current_path)
        if path_sum > goal:
            return
        if path_sum == goal:
            outcomes.append(current_path[:])
            return
        
        for idx, value in enumerate(options):
            current_path.append(value)
            # Pass subarray from current index to allow repeated use
            self.explore_combinations(options[idx:], goal, current_path, outcomes)
            current_path.pop()
    
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        solutions = []
        self.explore_combinations(candidates, target, [], solutions)
        return solutions

Combination Sum II

This variant requires each element to be used at most once and eliminates duplicate combinations in the result set.

Efficient deduplication is achieved during traversal rather than post-processing:

• Sort the candidate array so identical values become adjacent
• Use a tracking array to record whether an element has been used in the current branch
• Skip over elements that would create duplicate combinations at the same tree level

class Solution:
    def traverse_with_dedup(self, begin_pos, usage_flags, elements, limit, segment, results):
        segment_total = sum(segment)
        if segment_total > limit:
        if segment_total == limit:
            results.append(segment[:])
            return
        
        for pos in range(begin_pos, len(elements)):
            # Deduplicate at layer level
            if (pos > 0 and 
                elements[pos] == elements[pos-1] and 
                usage_flags[pos-1] == 0):
                continue
                
            segment.append(elements[pos])
            usage_flags[pos] = 1
            self.traverse_with_dedup(pos + 1, usage_flags, elements, limit, segment, results)
            segment.pop()
            usage_flags[pos] = 0
    
    def combinationSum2(self, candidates, target):
        final_results = []
        if sum(candidates) < target:
            return final_results
            
        candidates.sort()
        flags = [0] * len(candidates)
        self.traverse_with_dedup(0, flags, candidates, target, [], final_results)
        return final_results

Palindrome Partitioning

The task involves splitting a string into substrings where each substring is a palindrome.

The backtracking strategy treats string segmentation similarly to combination generation:

• Instead of selecting individual elements, contiguous substrings are evaluated
• A helper function checks if a substring is palindromic using two pointers
• Recursion continues until the entire string is processed

class Solution:
    def generate_partitions(self, text, current_segments, all_partitions, start_position):
        if start_position == len(text):
            all_partitions.append(current_segments[:])
            return
        
        for end_position in range(start_position, len(text)):
            substring = text[start_position:end_position + 1]
            if self.check_palindrome(substring):
                current_segments.append(substring)
                self.generate_partitions(text, current_segments, all_partitions, end_position + 1)
                current_segments.pop()
    
    def check_palindrome(self, sequence):
        left_pointer, right_pointer = 0, len(sequence) - 1
        while left_pointer < right_pointer:
            if sequence[left_pointer] != sequence[right_pointer]:
                return False
            left_pointer += 1
            right_pointer -= 1
        return True
    
    def partition(self, s: str) -> List[List[str]]:
        valid_partitions = []
        self.generate_partitions(s, [], valid_partitions, 0)
        return valid_partitions