[[Recursion]]

Problem

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:

Input: candidates = [2,3,6,7], target = 7 **Output:** [[2,2,3],[7]] Explanation: 2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times. 7 is a candidate, and 7 = 7. These are the only two combinations.

Example 2:

Input: candidates = [2,3,5], target = 8 Output: `[[2,2,2,2],[2,3,3],[3,5]]

Example 3:

Input: candidates = [2], target = 1 Output: []

Brainstorming idea

at any given index of the candidates we have 2 options either choose that number again or should i choose the next number the undo part is if the current subset of candidates whether duplicate or not is greater than the target then we just discard the last value i.e subset.pop()

the success is if the current subset sum is equal to target then we add it as a valid set

the question is what if the sum is partially correct ie less than target should we discard the whole subset and start from scratch or do we continue with it

candidates = [2,3,6,7]
target = 7
all_subsets = []
def generate_combination_sum(current_subset, index, candidates):
	if index == len(candidates) -1: # we have explored all candidates for this branch
		return
	if sum(current_subset) == target:
		all_subset.append(list(current_subset))
		return
	if sum(current_subset) > target:
		current_subset.pop()
		return
	
	# choose
	current_subset.append(candidates[index]) # add the element in current index
	# explore
	# 1. we explore duplicates
	generate_combination_sum(current_subset, index, candidates)
	# 3. we explore uniques
	generate_combintion_sum(current_subset, index+1, candidates)
	# lets assume that we discard completely and start from scratch
	current_subset = []

generate_combination_sum([], 0, candidates)

we need a way to explore with and without current index as well as with and without duplicates while making sure we pop in the correct order the last element or we have a clean slate for the whole subset to start from scratch

Optimal solution

This is a fantastic start, and you are asking exactly the right questions. You have correctly identified almost all the key components of a backtracking solution. Let’s refine your ideas.

Your Insights (Excellent!):

1. The Core Decision: You nailed it: “at any given index… either choose that number again or… choose the next number.” This is the central choice that defines the recursion.
2. Success & Failure Conditions: You correctly identified the base cases: sum == target (success) and sum > target (failure/prune).
3. The “Undo”: You’re right that pop() is the “undo” mechanism.

Your Question (The Heart of the Problem):

“what if the sum is partially correct ie less than target should we discard the whole subset and start from scratch or do we continue with it”

You continue with it! This is the “Explore” step. A current_subset with a sum less than the target is a valid partial solution that we need to keep building upon. Discarding it would mean you could never build a solution with more than one number.

Let’s Address the Issues in Your Pseudocode:

1. The “Undo” Placement is Incorrect:

   • if sum(current_subset) > target: current_subset.pop()
   • This is problematic. The pop() should always be paired with its corresponding append. It should happen after a recursive call returns, to undo the choice that led to that call. Placing it in the failure base case breaks this symmetry.

2. Confusing Exploration Paths:

   • You have two recursive calls, one with index and one with index+1. This correctly models the “use this element again” vs “move to the next element” idea.
   • However, the state management is tangled. After the first call (generate_combination_sum(..., index, ...)), current_subset is still modified. The second call then operates on this modified state, which is not what you want.

Let’s Re-structure the “Choose, Explore, Undo” Logic:

Let’s use a standard backtracking structure. Our function is dfs(start_index, current_subset, current_sum).

• State:
  • start_index: To avoid duplicate combinations like [2,3] and [3,2], we will only ever choose numbers at or after the current start_index.
  • current_subset: The combination we are building.
  • current_sum: Tracking the sum is more efficient than recalculating sum(current_subset) every time.

Inside dfs(start_index, current_subset, current_sum):

1. Base Cases (Success and Failure):

   • if current_sum == target: -> Found a solution. Add a copy of current_subset to results. Return.
   • if current_sum > target: -> This path is invalid. Stop exploring. Return.

2. The “Choices” (The Loop):

   • To make a choice for the next number to add, we can iterate through the candidates.
   • for i from start_index to len(candidates)-1: similar to [[Permutations]]
     • This loop says: “I’m going to try adding candidates[i] to my current_subset.”
     • The start_index ensures we don’t go backward. For [2,3,5], if we’ve picked 3, the next for loop will start from 3’s index, only allowing us to pick 3 or 5, but never 2. This prevents duplicate combinations.

3. The “Choose, Explore, Undo” inside the loop:

   • Choose:
     • current_subset.append(candidates[i])
     • current_sum += candidates[i]
   • Explore:
     • Make a recursive call. Now, what should the start_index for this call be? Since we can reuse the same number, we should allow the next recursive call to also choose from candidates[i]. So, we recurse with i.
     • dfs(i, current_subset, current_sum)
   • Undo:
     • After the recursive call returns, we must undo our choice to prepare for the next iteration of the for loop (where we will try candidates[i+1]).
     • current_subset.pop()
     • current_sum -= candidates[i]

DFS version

candidates = [2,3,5]
target = 8

all_subsets = []

def dfs_combinational_sum(start_index, current_subset, current_sum):
	if current_sum > target:
		return
		
	if current_sum == target:
		all_subsets.append(list(current_subset))
		return
		
	
	for i in range(start_index, len(candidates)): # this will take care of getting new elements from the remaining candidates
		current_subset.append(candidates[i]) # this will make sure we count duplicates too 
		current_sum +=candidates[i] # to make sure that we don't do sum again and again
		dfs_combinational_sum(i,current_subset,current_sum)
		# this will remove both the duplicate or the new element 
		current_subset.pop()
		current_sum -=candidates[i]

dfs_combinational_sum(0,[],0)	
print(all_subsets)