链接：https://leetcode.cn/problems/increasing-subsequences/solution/-by-xun-ge-v-6fmq/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 

题目

示例

思路

解题思路
本题我们使用递归枚举所有递增子序列，并且保存有效的子序列，在枚举过程中，我们可以判断前后元素的大小值，只当遇到前者小后者大时，才进行下一次递归，同时申请一个数组，进行同层去重

代码注释超级详细

代码

/**
 * 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().
 */
void backtracking(int* nums, int numsSize, int** res, int* returnSize, int** returnColumnSizes, int* path, int pathSize, int startIndex) {
    /* 终止条件，元素个数大于等于2个 */
    if (pathSize >= 2) {
        /* 为当前返回值分配空间 */
        res[*returnSize] = (int*)malloc(sizeof(int) * pathSize);
        /* 赋值 */
        memcpy(res[*returnSize], path, sizeof(int) * pathSize);
        /* 当前返回值的列数 */
        (*returnColumnSizes)[*returnSize] = pathSize;
        /* 返回行数加一 */
        (*returnSize)++;
    }
    /* 当前层使用过的元素，每一层都有会有一个这样的used数组 */
    int used[201] = {0};
    for (int i = startIndex; i < numsSize; i++) {
        /* 当前路径中的当前元素小于上一个元素、或者当前中当前元素之前以及使用过 */
        if ((pathSize > 0 && nums[i] < path[pathSize - 1]) || used[nums[i] + 100] == 1) {
            continue;
        }
        /* 记录当路径数组中 */
        path[pathSize] = nums[i];
        /* 因为此题输入元素在-100到100之间，使用加100这个操作，
         * 使得used中的下表落在0到200之间，这样就可以记录当前层元素的使用情况
         */
        used[nums[i] + 100] = 1;
        backtracking(nums, numsSize, res, returnSize, returnColumnSizes, path, pathSize + 1, i + 1);
    }
    return;
}

int** findSubsequences(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    /* 返回数组行数 */
    *returnSize = 0;
    /* 特判，递增子序列最少需要两个元素 */
    if (numsSize < 2) {
        return NULL;
    }
    /* 返回数组中每一行的列数 */
    *returnColumnSizes = (int*)malloc(sizeof(int) * 32768);
    /* 返回数组 */
    int** res = (int**)malloc(sizeof(int*) * 32768);
    /* 当前路径数组 */
    int path[numsSize];
    backtracking(nums, numsSize, res, returnSize, returnColumnSizes, path, 0, 0);
    return res;
}


作者：xun-ge-v
链接：https://leetcode.cn/problems/increasing-subsequences/solution/-by-xun-ge-v-6fmq/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。