Sponsored
Sponsored
This approach uses backtracking to generate permutations and a boolean array to track used elements in the current permutation combination. By sorting the array at the start, we can easily skip duplicates.
Time Complexity: O(n * n!) due to the generation of all permutations.
Space Complexity: O(n!) for storing the permutations and O(n) for the recursion stack.
1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5void backtrack(int* nums, int numsSize, bool* used, int* current, int pos, int** results, int* returnSize, int* returnColumnSizes) {
6 if (pos == numsSize) {
7 results[*returnSize] = malloc(numsSize * sizeof(int));
8 for (int i = 0; i < numsSize; ++i) {
9 results[*returnSize][i] = current[i];
10 }
11 returnColumnSizes[*returnSize] = numsSize;
12 (*returnSize)++;
13 return;
14 }
15 for (int i = 0; i < numsSize; ++i) {
16 if (used[i] || (i > 0 && nums[i] == nums[i-1] && !used[i-1])) continue;
17 used[i] = true;
18 current[pos] = nums[i];
19 backtrack(nums, numsSize, used, current, pos+1, results, returnSize, returnColumnSizes);
20 used[i] = false;
21 }
22}
23
24int** permuteUnique(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
25 *returnSize = 0;
26 *returnColumnSizes = malloc(sizeof(int) * 1000);
27 int** results = malloc(sizeof(int*) * 1000);
28 int* current = malloc(sizeof(int) * numsSize);
29 bool* used = calloc(numsSize, sizeof(bool));
30 qsort(nums, numsSize, sizeof(int), cmpfunc);
31 backtrack(nums, numsSize, used, current, 0, results, returnSize, *returnColumnSizes);
32 free(current);
33 free(used);
34 return results;
35}
36
37int cmpfunc(const void* a, const void* b) {
38 return (*(int*)a - *(int*)b);
39}
40
41int main() {
42 int nums[] = {1, 1, 2};
43 int size;
44 int* returnColumnSizes;
45 int** result = permuteUnique(nums, 3, &size, &returnColumnSizes);
46 for (int i = 0; i < size; ++i) {
47 for (int j = 0; j < returnColumnSizes[i]; ++j) {
48 printf("%d ", result[i][j]);
49 }
50 printf("\n");
51 free(result[i]);
52 }
53 free(result);
54 free(returnColumnSizes);
55 return 0;
56}The C solution uses backtracking with additional space to store used flags. It handles duplicates by comparing against previous elements after sorting the input array.
This method carries out permutations by recursively swapping elements and employs a set to track unique permutations and avoid generating duplicate results. It does not require sorting initially but uses swaps directly to generate permutations.
Time Complexity: O(n * n!)
Space Complexity: O(n * n!) because of the set used to store permutations.
1function permuteUnique(nums) {
The JavaScript implementation suits series swapping along with converting array entries to strings for set storage, achieving uniqueness by reshaping results when retrieving.