Problem Statement:
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 <= 10-10 <= nums[i] <= 10- All the integer of
numsare unique.
Approach:
Maintain a patharray for the current permutation.- At each step, try
adding an unused elementfrom arr. - If
path length equalsn, push a copy to result. - Backtrack by removing the last element and trying the next option.
Time Complexity:
Time Complexity = O(n × n!)
Space Complexity:
Space Complexity = O(n) for recursion + O(n!) output storage.
Dry Run
Input: arr = [1, 2, 3]
Step 0: Start Function backtrackSubsets([1, 2, 3])
n = 3
Initialize:
result = []
path = []
Call backtrack([], 0)
→ Push [] → result = [[]]
Loop i = 0 → arr[0] = 1
path.push(1) → path = [1]
Call backtrack([1], 1)
→ Push [1] → result = [[], [1]]
Loop i = 1 → arr[1] = 2
path.push(2) → path = [1, 2]
Call backtrack([1, 2], 2)
→ Push [1, 2] → result = [[], [1], [1, 2]]
Loop i = 2 → arr[2] = 3
path.push(3) → path = [1, 2, 3]
Call backtrack([1, 2, 3], 3)
→ Push [1, 2, 3] → result = [[], [1], [1, 2], [1, 2, 3]]
Loop ends (start = 3 >= n)
path.pop() → path = [1, 2]
Loop ends
path.pop() → path = [1]
Loop i = 2 → arr[2] = 3
path.push(3) → path = [1, 3]
Call backtrack([1, 3], 3)
→ Push [1, 3] → result = [[], [1], [1, 2], [1, 2, 3], [1, 3]]
Loop ends
path.pop() → path = [1]
Loop ends
path.pop() → path = []
Loop i = 1 → arr[1] = 2
path.push(2) → path = [2]
Call backtrack([2], 2)
→ Push [2] → result = [[], [1], [1, 2], [1, 2, 3], [1, 3], [2]]
Loop i = 2 → arr[2] = 3
path.push(3) → path = [2, 3]
Call backtrack([2, 3], 3)
→ Push [2, 3] → result = [..., [2, 3]]
Loop ends
path.pop() → path = [2]
Loop ends
path.pop() → path = []
Loop i = 2 → arr[2] = 3
path.push(3) → path = [3]
Call backtrack([3], 3)
→ Push [3] → result = [..., [3]]
Loop ends
path.pop() → path = []
Step 3: End
Return result = [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
Output:
[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
Explanation: The backtracking algorithm pushes the current path to result at every call, then iterates choices from start to n-1. For each choice, it adds the element, recurses to explore deeper subsets, and then removes the element (backtracks) to explore the next choice.
var permute = function(arr) {
let result = [];
let n = arr.length;
let backtrack = (path) => {
if(path.length === n){
result.push([...path]);
}
for(let i=0; i < n; i++){
if(!path.includes(arr[i])){
path.push(arr[i]);
backtrack(path);
path.pop();
}
}
}
backtrack([]);
return result;
};
def permute(arr):
result = []
n = len(arr)
def backtrack(path):
if len(path) == n:
result.append(path[:])
return
for i in range(n):
if arr[i] not in path:
path.append(arr[i])
backtrack(path)
path.pop()
backtrack([])
return result
# Example
arr = [1, 2, 3]
res = permute(arr)
for r in res:
print(r)
public class Main {
static void backtrack(List arr, List path, List> result, int n) {
if (path.size() == n) {
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < n; i++) {
if (!path.contains(arr.get(i))) {
path.add(arr.get(i));
backtrack(arr, path, result, n);
path.remove(path.size() - 1);
}
}
}
static List> permute(List arr) {
List> result = new ArrayList<>();
backtrack(arr, new ArrayList<>(), result, arr.size());
return result;
}
public static void main(String[] args) {
List arr = Arrays.asList(1, 2, 3);
List> res = permute(arr);
for (List list : res) {
System.out.println(list);
}
}
}
void backtrack(vector &arr, vector &path, vector> &result, int n) {
if (path.size() == n) {
result.push_back(path);
return;
}
for (int i = 0; i < n; i++) {
if (find(path.begin(), path.end(), arr[i]) == path.end()) {
path.push_back(arr[i]);
backtrack(arr, path, result, n);
path.pop_back();
}
}
}
vector> permute(vector &arr) {
vector> result;
vector path;
backtrack(arr, path, result, arr.size());
return result;
}
int main() {
vector arr = {1, 2, 3};
vector> res = permute(arr);
for (auto &v : res) {
for (int x : v) cout << x << " ";
cout << endl;
}
return 0;
}
void printPermutation(int *path, int n) {
for (int i = 0; i < n; i++) printf("%d ", path[i]);
printf("\n");
}
bool contains(int *path, int pathSize, int val) {
for (int i = 0; i < pathSize; i++)
if (path[i] == val) return true;
return false;
}
void backtrack(int *arr, int *path, int n, int pathSize) {
if (pathSize == n) {
printPermutation(path, n);
return;
}
for (int i = 0; i < n; i++) {
if (!contains(path, pathSize, arr[i])) {
path[pathSize] = arr[i];
backtrack(arr, path, n, pathSize + 1);
}
}
}
int main() {
int arr[] = {1, 2, 3};
int n = sizeof(arr) / sizeof(arr[0]);
int *path = (int*)malloc(n * sizeof(int));
backtrack(arr, path, n, 0);
free(path);
return 0;
}
class Program {
static void Backtrack(List arr, List path, List> result, int n) {
if (path.Count == n) {
result.Add(new List(path));
return;
}
for (int i = 0; i < n; i++) {
if (!path.Contains(arr[i])) {
path.Add(arr[i]);
Backtrack(arr, path, result, n);
path.RemoveAt(path.Count - 1);
}
}
}
static List> Permute(List arr) {
var result = new List>();
Backtrack(arr, new List(), result, arr.Count);
return result;
}
static void Main() {
var arr = new List { 1, 2, 3 };
var res = Permute(arr);
foreach (var list in res) {
Console.WriteLine(string.Join(" ", list));
}
}
}
