Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
Example 1:
Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Example 2:
Input: nums = [0,1] Output: [[0,1],[1,0]]
Example 3:
Input: nums = [1] Output: [[1]]
Constraints:
1 <= nums.length <= 6-10 <= nums[i] <= 10nums are unique.The Permutations problem asks you to generate every possible ordering of the elements in a given array. Since each element must appear exactly once in every ordering, the most common and effective strategy is backtracking.
The idea is to build permutations step by step. At each position, you choose an unused number, add it to the current path, and recursively continue building the permutation. Once the current path reaches the same length as the input array, you record it as a valid permutation. After exploring that branch, you backtrack by removing the last element and trying other unused choices.
A common implementation uses a visited array or performs in-place swapping to track which elements are already included. Because every permutation must be generated, the algorithm explores a factorial number of possibilities. This approach ensures all permutations are explored systematically while keeping the recursion tree manageable.
The overall time complexity grows factorially with the size of the array, which is unavoidable since the output itself contains all permutations.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Backtracking (Visited Array) | O(n × n!) | O(n) |
| Backtracking (In-place Swapping) | O(n × n!) | O(n) |
NeetCode
This approach uses recursion combined with backtracking to generate all possible permutations of the input array. The algorithm works by swapping elements of the array and recursively building permutations by fixing one element at a time until the entire array is permutated.
Time Complexity: O(n * n!) as there are n! permutations and we copy each permutation.
Space Complexity: O(n!) for storing the permutations, plus additional space used by the recursive stack.
1#include <stdio.h>
2
3void swap(int* a, int* b) {
4 int temp = *a;
5 *a = *b;
6 *b = temp;
7}
8
9void backtrack(int* nums, int numsSize, int start, int** result, int* returnSize, int* returnColumnSizes) {
10 if (start == numsSize) {
11 result[*returnSize] = (int*)malloc(sizeof(int) * numsSize);
12 for (int i = 0; i < numsSize; i++) {
13 result[*returnSize][i] = nums[i];
14 }
15 returnColumnSizes[*returnSize] = numsSize;
16 (*returnSize)++;
17 } else {
18 for (int i = start; i < numsSize; i++) {
19 swap(&nums[start], &nums[i]);
20 backtrack(nums, numsSize, start + 1, result, returnSize, returnColumnSizes);
21 swap(&nums[start], &nums[i]);
22 }
23 }
24}
25
26int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
27 int factorial = 1;
28 for (int i = 2; i <= numsSize; i++) {
29 factorial *= i;
30 }
31 int** result = (int**)malloc(sizeof(int*) * factorial);
32 *returnColumnSizes = (int*)malloc(sizeof(int) * factorial);
33 *returnSize = 0;
34 backtrack(nums, numsSize, 0, result, returnSize, *returnColumnSizes);
35 return result;
36}
37
38int main() {
39 int nums[] = {1, 2, 3};
40 int returnSize;
41 int* returnColumnSizes;
42 int** result = permute(nums, 3, &returnSize, &returnColumnSizes);
43 for (int i = 0; i < returnSize; i++) {
44 for (int j = 0; j < returnColumnSizes[i]; j++) {
45 printf("%d ", result[i][j]);
46 }
47 printf("\n");
48 }
49 for (int i = 0; i < returnSize; i++) {
50 free(result[i]);
51 }
52 free(result);
53 free(returnColumnSizes);
54 return 0;
55}
56This solution provides a C implementation using the backtracking approach. The backtrack function swaps elements to fix positions and calls itself recursively to generate permutations. Whenever a complete permutation is reached (start == numsSize), it is added to the result list. Swapping is undone as part of backtracking when going back up the call stack.
An alternative iterative approach utilizes a queue to generate permutations level by level by inserting each number at every possible position within every possible permutation.
Time Complexity: O(n * n!), iterating through permutations.
Space Complexity: O(n!) for storing permutations, constant space for current permutation array.
1#include
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, permutations is a classic backtracking problem frequently discussed in technical interviews, including FAANG-style interviews. It tests understanding of recursion, backtracking, and systematic exploration of search spaces.
The optimal approach is backtracking. You recursively build permutations by choosing unused elements and exploring all possible branches. This guarantees every valid ordering is generated while keeping the logic structured and manageable.
Generating permutations requires exploring every possible ordering of the elements, which results in n! permutations. Since each permutation may require copying or building a sequence of length n, the total time complexity is typically O(n × n!).
Most solutions use arrays or lists along with a boolean visited array to track which elements are already used. Another efficient technique is in-place swapping within the input array to generate permutations without extra tracking space.
This C implementation illustrates an iterative method for generating permutations using a next permutation generator. Each permutation is based on modifying and reversing array segments to derive the next permutation sequence, iteratively processed.