The combination sum of C language power deduction question 39. Backtracking method and traversal method

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 press In any order Return these combinations .

candidates Medium The same Numbers can Unlimited repeat selected . 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 .

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 : []

Tips ：

    1 <= candidates.length <= 30
    1 <= candidates[i] <= 200
    candidate Every element in is Different from each other
    1 <= target <= 500

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/combination-sum
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Thought analysis ：

Method 1 ： backtracking

According to the example 1： Input : candidates = [2, 3, 6, 7],target = 7.

    There are... In the candidate array 2, If a combination is found, the sum is 7 - 2 = 5 All combinations of , Add... Before 2 , Namely 7 All combinations of ;
    In the same way 3, If a combination is found, the sum is 7 - 3 = 4 All combinations of , Add... Before 3 , Namely 7 All combinations of , Find it in this order .

Based on the above ideas , You can draw the following tree diagram . I suggest you draw this tree on paper , This kind of problem needs to draw a tree diagram first , And then coding implementation .

Code through Depth-first traversal Realization , Use a list , stay Depth-first traversal In the process of change , Traverse all possible lists and judge whether the current list meets the requirements of the topic , Become a backtracking algorithm .

• With target = 7 by Root node , Subtract when creating a branch ;
• Each arrow indicates ： Subtract the value on the edge from the value of the parent node , Get the value of the child node . The value of the edge is given in the title candidate The value of each element of the array ;
• Reduced to 000 Or stop when it's negative , namely ： node 000 And negative nodes become leaf nodes ;
• All from root node to node 000 The path of （ Only from top to bottom , There's no loop ） This is the result of the topic .

But only considering this will produce repetition .

The optimization is as follows ： From the... Of each floor 222 Start with a node , Can no longer search to generate nodes of the same layer that have been used candidate Elements in .

  Method 2 ： Ergodic method

The most important thing of traversal is to determine the number of traversals

In fact, it can be thought that if the maximum length of the combination that conforms to the meaning of the question can be determined a, So you can use it a Time for Cycle through , And this a Is available , Just use target Divide by the smallest value in the array to get theoretically , The maximum length of the combination . Then there is another problem, that is, how to write a a Time of for loop , Recursion can do it , stay for Recursion is used in the loop . The final performance is slower than the backtracking algorithm

int *path;
int pathTop;
int **result;
int resultTop;
int *length;

void backTrack(int *candidates,int candidatesSize,int target, int sum , int index){
    if(sum>target)
        return ;
    if(sum == target){
        int *temp = malloc(sizeof(int)*pathTop);
        for(int i=0;i<pathTop;i++){
            temp[i] = path[i];
        }
        result[resultTop] = temp;
        length[resultTop++] = pathTop;
        return ;
    }
    for(int j=index; j<candidatesSize && sum<=target;j++){
        sum = sum + candidates[j];
        path[pathTop++] = candidates[j];
        backTrack(candidates,candidatesSize,target,sum,j);
        sum = sum - candidates[j];
        pathTop--;
    }
}

int** combinationSum(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes){
    pathTop = resultTop = 0;
    path = malloc(sizeof(int)*100);
    result = malloc(sizeof(int*) *500);
    length = malloc(sizeof(int) *500);
    backTrack(candidates,candidatesSize,target,0,0);
    *returnSize = resultTop;
    *returnColumnSizes = malloc(sizeof(int) *500);
    for(int i =0 ; i<resultTop ; i++){
        (*returnColumnSizes)[i] = length[i];
    }
    return result;
}