[39] Combination Sum

本來想用dp的算有幾種來延伸，發現是一場災難Orz

原來要用backtracking，然後原來backtracking 的template 就是tree的traversal時使用的DFS啊啊啊啊啊（倒退十五步）

發現是這樣之後幾乎一次過了....覺得前面瞎弄三五天不知道是在幹嘛......Orz

/**

* 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().

*/

#define MAXLEN 150

void backtracking(int *curr, int currIdx ,int **ret, int* candidates,

int candidatesSize,int canIdx ,int target, int* returnSize,

int** returnColumnSizes)

{

if (target < 0) //return

return;

if (target == 0) //output to ret

{

ret[(*returnSize)]= calloc (currIdx, sizeof(int));

(*returnColumnSizes)[(*returnSize)] = currIdx;

#if 1

for (int i=0;i<currIdx;i++)

ret[(*returnSize)][i]= curr[i];

#else

memcpy(ret[(*returnSize)], curr, currIdx * sizeof(int));

#endif

(*returnSize)++;

return;

}

for (int i=canIdx ; i<candidatesSize; i++)

{

curr[currIdx] = candidates[i];

backtracking(curr, currIdx+1 ,ret, candidates, candidatesSize,i,

target- candidates[i], returnSize, returnColumnSizes);

}

return;

}

int** combinationSum(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes){

int **ret = calloc (MAXLEN, sizeof(int*));

(*returnColumnSizes)= calloc (MAXLEN, sizeof(int));

(*returnSize) =0;

int *curr = calloc (MAXLEN, sizeof(int));

backtracking(curr, 0 ,ret, candidates, candidatesSize, 0,

target, returnSize, returnColumnSizes);

return ret;

}