【回溯】递增子序列

解题思路：回溯算法

1.如果path中数组元素个数大于1，将path复制放入ans中

2.树每一层都要创建一个数组uset用来记录用过的结点

3.从当前startIndex开始，到数组结尾结束，遍历数组：

a.如果当前元素小于path最顶层元素||在uset中找到当前元素，则continue

b.若不符合，则将当前元素加入path，同时加入uset，进行回溯。回溯结束后，path弹出最顶部元素

int* path;
int pathTop;
int** ans;
int ansTop;
int* length;
void copy() {
    int* tempPath = (int*)malloc(sizeof(int) * pathTop);
    memcpy(tempPath, path, pathTop * sizeof(int));
    length[ansTop] = pathTop;
    ans[ansTop++] = tempPath;
}

int find(int* uset, int usetSize, int key) {
    int i;
    for(i = 0; i < usetSize; i++) {
        if(uset[i] == key)
            return 1;
    }
    return 0;
}

void backTracking(int* nums, int numsSize, int startIndex) {
    if(pathTop > 1) {
        copy();
    }
    int* uset = (int*)malloc(sizeof(int) * numsSize);
    int usetTop = 0;
    int i;
    for(i = startIndex; i < numsSize; i++) {
        if((pathTop > 0 && nums[i] < path[pathTop - 1]) || find(uset, usetTop, nums[i]))
            continue;
        uset[usetTop++] = nums[i];
        path[pathTop++] = nums[i];
        backTracking(nums, numsSize, i + 1);
        pathTop--;
    }
}

int** findSubsequences(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
    path = (int*)malloc(sizeof(int) * numsSize);
    ans = (int**)malloc(sizeof(int*) * 33000);
    length = (int*)malloc(sizeof(int*) * 33000);
    pathTop = ansTop = 0;

    backTracking(nums, numsSize, 0);

    *returnSize = ansTop;
    *returnColumnSizes = (int*)malloc(sizeof(int) * ansTop);
    int i;
    for(i = 0; i < ansTop; i++) {
        (*returnColumnSizes)[i] = length[i];
    }
    return ans;
}