[回溯算法]leetcode40. 组合总和 II(c实现)

题目

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 注意：解集不能包含重复的组合。  示例 1: 输入: candidates = [10,1,2,7,6,1,5], target = 8, 输出: [ [1,1,6], [1,2,5], [1,7], [2,6] ] 示例 2: 输入: candidates = [2,5,2,1,2], target = 5, 输出: [ [1,2,2], [5] ]  

代码

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
 int *path;
 int pathTOP;
 int **ans;
 int  ansTOP;
 int *length;
 void backtracking(int*candidates,int candidatesSize,int target,int sum,int startindex)
 {
     int i=0;
     if(sum>target)
     {
         return ;
     }
     //递归终止条件
     if(sum==target)
     {
        int*temp=(int*)malloc(sizeof(int)*pathTOP);
        for(i=0;i<pathTOP;i++)
        {
          temp[i]=path[i];
        }
         ans[ansTOP]=temp;
         length[ansTOP++]=pathTOP;
         return ;
     }
     for(i=startindex;i<candidatesSize;i++)
     {
         if(i>startindex&&candidates[i-1]==candidates[i])
         //判断是否用于去重，若为树层则需去重
         {
             continue;
         }
         path[pathTOP++]=candidates[i];
         sum+=candidates[i];
         backtracking(candidates,candidatesSize,target,sum,i+1);
         //回溯
         sum-=candidates[i];
         pathTOP--;
     }
 }
 int cmp(const void*e1,const void*e2)
 {
     return *((int*)e1)-*((int*)e2);
 }
int** combinationSum2(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes){
      path=(int*)malloc(sizeof(int)*50);
      ans=(int**)malloc(sizeof(int*)*200);
      length=(int*)malloc(sizeof(int)*200);
      pathTOP=0;
      ansTOP=0;
      int sum=0;//用于记录取值的加和，与traget判断
      int startindex=0;//用于记录起始位置
      qsort(candidates,candidatesSize,sizeof(int),cmp);
      backtracking(candidates,candidatesSize,target,sum,startindex);
      *returnSize=ansTOP;
      //记录每个集合中的大小
      *returnColumnSizes=(int*)malloc(sizeof(int)*ansTOP);
      int i=0;
      for(i=0;i<ansTOP;i++)
      {
          (*returnColumnSizes)[i]=length[i];
      }
       return ans;
}

过程

1.为什么要有去重操作

若不包括去重操作，那也就没有排序操作 因为组合是不分顺序的，所以像出现的 1 2 5 与 2 1 5实际是表示一个组合

2.分辨树层重复还是树层与树枝重复

这里以 1 1 2为例 我们要区分是树层的重复还是 树层与树枝的重复

这里产生了两个 1 2 组合 第一个 1 2 组合： 先在树层中取1，for循环中剩下 1 2 ，进入递归中，取树枝的1 这种 即为树层与树枝的重复 ，即便是两者值相同也不用去重

第二个 1 2 组合： 取树层的1后，发现再次进入for循环中，i=2,startindex仍等于1 i>startindex 同时 两者值相同 即判断树层中重复，需要去重

3.递归展开图