Problem
Given an array of distinct integers, return all possible permutations.
Example
Input: [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]Solution
Backtracking with a “used” flag for each element.
def permute(nums):
result = []
def backtrack(path, used):
if len(path) == len(nums):
result.append(path[:])
return
for i in range(len(nums)):
if used[i]: continue
used[i] = True
path.append(nums[i])
backtrack(path, used)
path.pop()
used[i] = False
backtrack([], [False] * len(nums))
return resultfunction permute(nums) {
const result = [];
const used = new Array(nums.length).fill(false);
function backtrack(path) {
if (path.length === nums.length) { result.push([...path]); return; }
for (let i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true;
path.push(nums[i]);
backtrack(path);
path.pop();
used[i] = false;
}
}
backtrack([]);
return result;
}void backtrack(vector<int>& nums, vector<int>& path, vector<bool>& used, vector<vector<int>>& result) {
if (path.size() == nums.size()) { result.push_back(path); return; }
for (int i = 0; i < nums.size(); i++) {
if (used[i]) continue;
used[i] = true;
path.push_back(nums[i]);
backtrack(nums, path, used, result);
path.pop_back();
used[i] = false;
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result;
vector<int> path;
vector<bool> used(nums.size(), false);
backtrack(nums, path, used, result);
return result;
}public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
boolean[] used = new boolean[nums.length];
backtrack(nums, new ArrayList<>(), used, result);
return result;
}
private void backtrack(int[] nums, List<Integer> path, boolean[] used, List<List<Integer>> result) {
if (path.size() == nums.length) { result.add(new ArrayList<>(path)); return; }
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true;
path.add(nums[i]);
backtrack(nums, path, used, result);
path.remove(path.size() - 1);
used[i] = false;
}
}Complexity
- Time: O(n * n!)
- Space: O(n)
Explanation
For each position, try every unused element. The “used” array prevents revisiting elements within the same permutation.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?