[数据结构与算法]491. 递增子序列

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

示例 1：

输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
示例 2：

输入：nums = [4,4,3,2,1]
输出：[[4,4]]

提示：

1 <= nums.length <= 15
-100 <= nums[i] <= 100

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/increasing-subsequences
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：这个题目的关键在于如何找到同层下一个符合条件的节点，同层的节点不能有重复，同时同一条分支上面的节点要保证是底层的顺序，所以就需要在同层搜索的时候进行限制，找到合法的节点，其余的都是模板的步骤，顺序实现即可

/**
 * 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 start, int* nums, int numsSize, int** ans, int* returnSize, int* col, int* path, int pathSize)
{
    // 进行子集收集
    if (pathSize > 1) {
        ans[*returnSize] = (int*)malloc(sizeof(int) * pathSize);
        int j;
        for (j = 0; j < pathSize; j++) {
            ans[*returnSize][j] = path[j];
        }
        col[(*returnSize)++] = pathSize;
    }
    
    // 深度递归搜索终止条件
    if (start >= numsSize) {
        return;
    }


    // 同层广度搜索 
    int i;
    for (i = start; i < numsSize; i++) {
        // 查找符合分支的下一个数 --- 关键的一步
        // 看下当前i位置的数是否符合条件，即大于等于path[pathSize - 1];  --- 最重要 
        if (pathSize > 0 && nums[i] < path[pathSize - 1]) continue;
        // 进行同层的去重
        int k, flag = 0;
        for (k = start; k < i; k++) {
            if (nums[i] == nums[k]) {
                flag = 1;
                break;
            }
        }
        
        if (flag == 1) continue;
        
        path[pathSize++] = nums[i];
        
        // 深度递归搜索
        backtracking(i + 1, nums, numsSize, ans, returnSize, col, path, pathSize);
        // 进行现场恢复
        pathSize--;
    }

}

int** findSubsequences(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){


    // 保存一个符合条件的子集的空间
    int* path = (int*)malloc(sizeof(int) * numsSize);
   // path[0] = nums[0];
    // 子集空间有多少元素
    int pathSize = 0;
    // 保存最后的结果
    int** ans = (int**)malloc(sizeof(int*) * 1008611);
    // 保存一个结果中一个子集有多少个元素
    int* col = (int*)malloc(sizeof(int) * 1008611);
    *returnColumnSizes = col;
    *returnSize = 0;

    if (numsSize < 2) return ans; 

    // 进行回溯计算
    backtracking(0, nums, numsSize, ans, returnSize, col, path, pathSize);

    return ans;
}