博客

leetcode 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

解答

#define MAXSIZE 100000
#define THREAD 2
#define NUMSIZE 300
int **g_res = NULL;
int g_row;
int *g_col = NULL;            
int *g_buf = NULL;
int g_index;

void backtrace(int* nums, int numsSize, int start) {
    if (g_index >= THREAD) {
        g_res[g_row]= (int *)malloc(sizeof(int) * g_index);
        memcpy(g_res[g_row], g_buf, sizeof(int) * g_index);
        g_col[g_row] = g_index;
        g_row++;
    }
    int selected[NUMSIZE] = { 0 };  // 记录本层使用过的值,如[4,6,7]
    for (int i = start; i < numsSize; i++) {
        // 剪枝：非递增||本层已选择过该值，如待选[7]，已选[4,6,7]
        if (g_index > 0 && nums[i] < g_buf[g_index - 1] || selected[nums[i] + 100] == 1) {
            continue;
        }
        selected[nums[i] + 100] = 1;
        g_buf[g_index++] = nums[i];
        backtrace(nums, numsSize, i + 1);
        g_index--;
    }
}

int** findSubsequences(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    g_res = (int **)malloc(sizeof(int *) * MAXSIZE);
    g_buf = (int *)malloc(sizeof(int) * numsSize);
    *returnColumnSizes = (int*)malloc(sizeof(int) * MAXSIZE);
    g_col= (int *)malloc(sizeof(int) * MAXSIZE);
    g_row = 0;
    g_index = 0;

    backtrace(nums, numsSize, 0);
    *returnSize = g_row;
    for (int i = 0; i < g_row; i++) {
        (*returnColumnSizes)[i] = g_col[i];
    }
    return g_res;
}