# 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 = 7Output: [[1,2,4]]Explanation:1 + 2 + 4 = 7`

Idea: list all the possible combinations:

`      ...[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],]`

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

Idea:

`combination      target      remain#1                 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                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`

--

--

Coding, implementing, optimizing ML annotation with self-supervised learning, TLDR: doctor’s labeling is the 1st priority for our Cervical AI project.