Problem 491: Non-decreasing Subsequences

Given an integer array nums, return all the different non-decreasing subsequences that have atleast two elements. The answer can be in any order. When two integers are equal, this counts as a valid increasing sequecne.

Example 1:

Input: nums = [4,6,7,7]
Output: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

Example 2:

Input: nums = [4,4,3,2,1]
Output: [[4,4]]

Constraints:

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

Deduplication Strategy

Unlike typical array deduplication problems, these two questions require element tracking because the original data order must be preserved. Sorting would destroy the sequence relationship.

The solution uses a visited array to track which elements have been used in the current path:

#include <stdlib.h>
#include <string.h>

int** result;
int resultSize;
int* currentPath;
int pathLength;

void generate(int* nums, int len, int* visited) {
    if (pathLength == len) {
        int* buffer = (int*)malloc(sizeof(int) * len);
        memcpy(buffer, currentPath, sizeof(int) * len);
        result[resultSize++] = buffer;
        return;
    }
    
    for (int i = 0; i < len; i++) {
        if (visited[i]) {
            continue;
        }
        visited[i] = 1;
        currentPath[pathLength++] = nums[i];
        generate(nums, len, visited);
        visited[i] = 0;
        pathLength--;
    }
}

int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    result = (int**)malloc(sizeof(int*) * 10000);
    currentPath = (int*)malloc(sizeof(int) * numsSize);
    resultSize = pathLength = 0;
    
    int* visited = (int*)calloc(numsSize, sizeof(int));
    generate(nums, numsSize, visited);
    
    *returnSize = resultSize;
    *returnColumnSizes = (int*)malloc(sizeof(int) * resultSize);
    for (int i = 0; i < resultSize; i++) {
        (*returnColumnSizes)[i] = numsSize;
    }
    
    free(visited);
    return result;
}

Problem 47: Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations in any order.

Example 1:

Input: nums = [1,1,2]
Output:
[[1,1,2],
 [1,2,1],
 [2,1,1]]

Example 2:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Constraints:

• 1 <= nums.length <= 8
• -10 <= nums[i] <= 10

Dual-layer Deduplication

This problem requires two types of deduplication:

1. Tree-level deduplication: Prevents selecting the same value twice at the same recursion depth
2. Branch-level deduplication: Prevents reusing an element already in the current permutation

Both layers use tracking mechanisms since sorting would break the requirement of returning complete permutations of the original length:

#include <stdlib.h>
#include <string.h>

int** result;
int resultSize;
int* currentPath;
int pathLength;

int contains(int* history, int size, int value) {
    for (int i = 0; i < size; i++) {
        if (history[i] == value) {
            return 1;
        }
    }
    return 0;
}

void generate(int* nums, int len, int* used) {
    if (pathLength == len) {
        int* buffer = (int*)malloc(sizeof(int) * len);
        memcpy(buffer, currentPath, sizeof(int) * len);
        result[resultSize++] = buffer;
        return;
    }
    
    int* levelHistory = (int*)malloc(sizeof(int) * len);
    int historyCount = 0;
    
    for (int i = 0; i < len; i++) {
        if (used[i] || contains(levelHistory, historyCount, nums[i])) {
            continue;
        }
        levelHistory[historyCount++] = nums[i];
        used[i] = 1;
        currentPath[pathLength++] = nums[i];
        generate(nums, len, used);
        used[i] = 0;
        pathLength--;
    }
    
    free(levelHistory);
}

int** permuteUnique(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    result = (int**)malloc(sizeof(int*) * 10000);
    currentPath = (int*)malloc(sizeof(int) * numsSize);
    resultSize = pathLength = 0;
    
    int* used = (int*)calloc(numsSize, sizeof(int));
    generate(nums, numsSize, used);
    
    *returnSize = resultSize;
    *returnColumnSizes = (int*)malloc(sizeof(int) * resultSize);
    for (int i = 0; i < resultSize; i++) {
        (*returnColumnSizes)[i] = numsSize;
    }
    
    free(used);
    return result;
}