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.
1import java.util.Arrays;
Java solution uses primitive swapping between indices to form permutations and relies on a Set for avoiding duplicates, allowing permutation logic to remain in-place and simple.