[backtracking] backtracking method to solve combinatorial problems

• subject 1： Given two integers n and k, Return range [1, n] All the possibilities in k Combination of numbers . You can press In any order Return to the answer .
  Example 1：
  Input ：n = 4, k = 2
  Output ：
  [[2,4], [3,4],[2,3],[1,2],[1,3],[1,4],]
  Topic link ：https://leetcode-cn.com/problems/combinations/

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        path = []
        res = []
        startindex = 1
        def backtracking(n, k, startindex):
            if len(path) == k:
                res.append(path[:])
                return 
            for i in range(startindex, n + 2 - (k -len(path))):  #  prune 
                path.append(i)
                backtracking(n, k, i + 1)
                path.pop()
            
        backtracking(n, k, startindex)
        return res

• subject 2： To give you one No repeating elements Array of integers for candidates And a target integer target , find candidates You can make the sum of numbers as the target number target Of all Different combinations , And return... As a list . You can return these combinations in any order .
  candidates The same in Numbers can be selected repeatedly without limit . If the selected number of at least one number is different , Then the two combinations are different .
  For a given input , Guarantee and for target The number of different combinations of is less than 150 individual .
  Example 1：
  Input ：candidates = [2,3,6,7], target = 7
  Output ：[[2,2,3],[7]]
  explain ：
  2 and 3 Can form a set of candidates ,2 + 2 + 3 = 7 . Be careful 2 You can use it multiple times .
  7 Is also a candidate , 7 = 7 .
  Only these two combinations
  Topic link ：https://leetcode-cn.com/problems/combination-sum/

#  Writing a ：
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        path = []
        def backtracking(candidates, target, startindex, sum_):
            if sum_ == target:
                res.append(path[:])
                return
            for i in range(startindex, len(candidates)):
            #  Write the original array like this candidates You don't have to sort , Because it will traverse all the numbers in this layer 
            #  If there is one that meets the conditions, continue , If it doesn't match, it will be traced back to the previous layer 
                if sum_ + candidates[i] <= target:  
                    sum_ += candidates[i]
                    path.append(candidates[i])
                    #  Can be reused , So when you go to the next level, you can still subscript i Start fetching at 
                    backtracking(candidates, target, i, sum_)  
                    sum_ -= candidates[i]
                    path.pop()

        backtracking(candidates, target, 0, 0)
        return res
#  Write two ：
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        path = []
        def backtracking(candidates, target, startindex, sum_):
            if sum_ == target:
                res.append(path[:])
                return
            for i in range(startindex, len(candidates)):
            #  In this way, the original array must be sorted from small to large , When  sum_ +  The next number is greater than target when ,
            #  Explain all the following numbers  + sum_ Is greater than target, At this point, you can stop the traversal of this layer , Go back directly to the previous layer 
                if sum_ + candidates[i] > target: return 
                sum_ += candidates[i]
                path.append(candidates[i])
                #  Can be reused , So when you go to the next level, you can still subscript i Start fetching at 
                backtracking(candidates, target, i, sum_)
                sum_ -= candidates[i]
                path.pop()
                
        candidates.sort()  #  Array must be sorted 
        backtracking(candidates, target, 0, 0)
        return res
"""  These two ways of writing have been pruned , But the specific writing is different   Method 2 ：  Sort the original array from small to large , When  sum_ +  The next number is greater than target when ,  Explain all the following numbers  + sum_ Is greater than target, At this point, you can stop the traversal of this layer , Go back directly to the previous layer   Method 1 ： If you go back to the previous level , All data of this layer must be judged , If there are qualified numbers on the way , Will go to the next layer , If not   If it meets the requirements, it will return to the previous level ,  Suppose we know that the data of this layer do not meet the conditions , But for the computer, it doesn't know, so it must judge once   Then you can go back to the previous level   contrast ： The second method is to spend a sorting time , Then gain time in each subsequent layer traversal   The first method is to save a sorting time , But it takes time in the subsequent traversal of each layer   Generally speaking, the second method is better   Method 1 I wrote , Method 2 someone else wrote ！（T-T） """

• subject 3： Given a set of candidate numbers candidates And a target number target , find candidates All can make numbers and target The combination of .
  candidates Each number in can only be used in each combination once .

  Example 1:
  Input : candidates = [10,1,2,7,6,1,5], target = 8,
  Output :[[1,1,6],[1,2,5],[1,7],[2,6]]
  Topic link ：https://leetcode-cn.com/problems/combination-sum-ii/

class Solution:
    def combinationSum2(self, candidates, target):
        path = []
        res = []
        def backtracking(candidates, target, startindex, sum_):
            if sum_ == target:
                res.append(path[:])
                return
            for i in range(startindex, len(candidates)):
                if sum_ + candidates[i] > target: return
                #  Judge whether it has been used in this layer  
                if i > startindex and candidates[i] == candidates[i-1]: continue
                sum_ += candidates[i]
                path.append(candidates[i])
                #  Can not be reused , So on the next floor i Cannot subscript from i+1 Start fetching at 
                backtracking(candidates, target, i + 1, sum_)
                sum_ -= candidates[i]
                path.pop()
        
        candidates.sort()  #  Here you must sort 
        backtracking(candidates, target, 0, 0)
        return res
"""  The difference between this question and the previous one is ：  The number in the previous array is not repeated , And it can be accessed repeatedly   The number in this array is repeated , And it can not be used repeatedly   This question is sorted first , In this way, the same data will be next to each other , Then when traversing each layer , Judge whether the number has been used in this layer   for example  1 1 1 2 2 2 3 3 3  Take... On the first floor  1    But when you go back to the first level of traversal, you can't get 1, Only from 2 Start   The remaining  1 1 2 2 2 3 3 3  The second layer can also take  1   But you can't go back to the second layer 1, Because this layer has been taken, it can only be taken from 2 Start   The remaining  1 2 2 2 3 3 3  You can also take 1  take 2   The first 2 When the following numbers are traversed back to this layer for times , You can't take 2,  For the first time, this floor is taken 2  Because the first 1 It has been used once in this layer   A little   """

The description of this topic is difficult to understand , You can refer to
Official and various Immortals' explanations ：https://leetcode-cn.com/problems/combination-sum-ii/solution/