【回溯】组合总和3

解题思路：回溯算法

递归结束条件：当数组中元素大于size大小或当path中剩余解法最小元素与其他元素之和大于n

变量：path记录当前途径 ans记录答案

创建数组traversal，参数为当前应填充的数字curNum，要达成的和sum，组合元素数量

1.for循环从当前数字curNum开始，一直遍历到10（因为数组中元素只能为1-9）

2.如果当前path中所有元素和相加等于sum且pathTop与k相等，则将path放入ans

3.递归进入下一层

4.将栈顶元素出栈

int* path;
int pathTop;
int** ans;
int ansTop;
int getPathSum() {
    int i;
    int sum = 0;
    for(i = 0; i < pathTop; i++) {
        sum += path[i];
    }
    return sum;
}

void traversal(int curNum, int size, int sum) {
    //若path中元素个数大于size或者path中所有元素总和大于sum
    if(pathTop > size-1 || (getPathSum() + curNum) > sum)
        return;
    int i;
    //从curNum开始遍历，一直遍历到10
    for(i = curNum; i < 10; i++) {
        //将当前元素入栈
        path[pathTop++] = i;
        //若入栈后path中元素总和等于sum且path中元素个数正好为size
        //拷贝path，放入ans中
        if(getPathSum() == sum && pathTop == size) {
            int* tempPath = (int*)malloc(sizeof(int) * size);
            int j;
            for(j = 0; j < size; j++) 
                tempPath[j] = path[j];
            ans[ansTop++] = tempPath;
        }
        traversal(i+1, size, sum);
        //将path最顶层元素出栈
        pathTop--;
    }
}

int** combinationSum3(int k, int n, int* returnSize, int** returnColumnSizes){
    //初始化辅助变量
    path = (int*)malloc(sizeof(int) * k);
    ans = (int**)malloc(sizeof(int*) * 20);
    pathTop = ansTop = 0;

    traversal(1, k, n);

    //设置返回的二维数组中元素个数为ansTop
    *returnSize = ansTop;
    //设置二维数组中每个元素个数的大小为k
    *returnColumnSizes = (int*)malloc(sizeof(int) * ansTop);
    int i;
    for(i = 0; i < ansTop; i++) {
        (*returnColumnSizes)[i] = k;
    }
    return ans;
}