An Easy Example to Show How the Recurse Work

I don’t like Recurse in programming, because it can go wild… Making it as simple as possible is a beautiful thing to do.

Example:

• for digit set [1,2,…,9], find k numbers that sum up to n. Each number is used at most once:

Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7

Idea: list all the possible combinations:

[1]  [2]  [3]  ...[9]
[1,2][1,3][1,4]...[1,9]
[1,2,3][1,2,4],[1,2,5]...[1,2,9]
...
[2,3][2,4][2,5]...[2,9]
[2,3,4][2,3,5][2,3,6]...[2,3,9]
...
[3,4][3,5][3,6]...[3,9]
[3,4,5][3,4,6][3,4,7]...[3,4,9]
...

following code will represent above idea:

def recurse_sum(S,digit):
  for d in range(digit,10):
    recurse_sum(S+[d],d+1)
recurse_sum([],1)

The full code :

def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        ans = set()
        def recurse_sum(S:List[int], digit:int ) -> None:
            #print(f"S={S}, digit={digit}")
            if len(S) == k and sum(S)== n:
                ans.add(tuple(S))
                return
            if len(S) > k:
                return
            for d in range(digit, 10):
                recurse_sum(S+[d], d+1)
            return
        recurse_sum([],1)
        return ans

Let's have another example:

given an integer list and a target :

 candidates = [2,3,6,7], target = 7

find all the combinations which sum up to the target:

[[2,2,3],[7]]

The combinations should be consisted of the list and allowed repeat.

Idea:

combination      target      remain
#1[2]                 7          5
#2[2,2]               7          3
#3[2,2,2]             7          1
#4[2,2,2,2]           7         -1  return to next
#5[2,2,2,3]           7         -2  return to next
#6[2,2,2,6]           7         -5  return to next
#7[2,2,2,7]           7         -6  return to #3.next=#8
#8[2,2,3]             7          0  return to next
#9[2,2,6]             7         -3  return
#10[2,2,7]            7         -4  return to #2.next=#11
#11[2,3]              7          2
#12[2,3,3]            7         -1  return to #11.next=#13
#13[2,6]              7         -1  return to #13.nezt=#14
#14[2,7]              7         -2  return to #1.nezt=#15
#15[3]                7         4
#16[3,3]              7         1
#17[3,3,3]            7         -2
#18[3,3,6]            7         -8

a recurse code will perform the above idea:

def recurse_sum(S, remain, start_i):
  if remain == 0:
     res.add(S)
     return
  if remain < 0: 
     return
  for i in range(start_i,len(candidates)):
     recurse_sum(S+[candidates[i],remain-candidate[i], i+1)

the last line can be written as following to be easier to understand:

     #recurse_sum([]+[candidates[i],remain-candidate[i], i+1)
     tmpS = S+[candidates[i]]
     recurse_sum(tmpS, target - sum(tmpS), i)

the full code:

def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = set()
        def recurse_sum(S:List[int], remain:int, start_i:int)->None:
            if remain == 0:
                res.add(tuple(S))
                return
            if remain < 0:
                return
            for i in range(start_i,len(candidates)):
               # recurse_sum(S+[candidates[i]], remain - candidates[i], i)
                tmpS = S+[candidates[i]]
                recurse_sum(tmpS, target - sum(tmpS), i)
        recurse_sum([],target,0) 
        return res