216. combined summation III enumeration method

216. Combinatorial summation III

Find the sum of all the sums n Of k Combination of numbers , And the following conditions are met ：

 Use only numbers 1 To 9
 Every number   Use it once at most  

return A list of all possible valid combinations . The list cannot contain the same combination twice , Combinations can be returned in any order .

Example 1:

Input : k = 3, n = 7
Output : [[1,2,4]]
explain :
1 + 2 + 4 = 7
There is no other matching combination .

Example 2:

Input : k = 3, n = 9
Output : [[1,2,6], [1,3,5], [2,3,4]]
explain :
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There is no other matching combination .

Example 3:

Input : k = 4, n = 1
Output : []
explain : There is no valid combination .
stay [1,9] Use... In scope 4 A different number , The minimum sum we can get is 1+2+3+4 = 10, because 10 > 1, No valid combination .

/** * 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 r[10]={
    1,1,1,1,1,1,1,1,1,1};
 int path[9];
 int **result;
 int resultTop=0;

 void dfs(int k,int n,int size,int val,int index ){
    
    int i;
    if(size==k&& val==n){
    
       
          int *temp = malloc(sizeof(int)*k);
            for(int i =0;i<k;i++){
    
                temp[i] = path[i];
            }
             
            result[resultTop++] = temp;

       
    }
     for(i=index+1;i<=9;i++){
    
         if(r[i]==1){
    
                r[i]=0;
                path[size]=i;
            dfs(k,n,size+1,val+i,i);
                   r[i]=1;
         }
       
     }
 }

 
int** combinationSum3(int k, int n, int* returnSize, int** returnColumnSizes){
    
    result = malloc(sizeof(int*) *90);
     resultTop=0;
      dfs(k,n,0,0,0);
        *returnSize = resultTop;
       
    *returnColumnSizes = malloc(sizeof(int*) * resultTop);
      for(int i=0 ; i<resultTop ; i++){
    
        (*returnColumnSizes)[i] = k;
    }
    return  result;


    

}