Amazon
Apple
ByteDance
Microsoft
Oracle
Paypal
eBay
2021-04-29
46. Permutations
Question:
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] <= 10- All the integers of
numsare unique.
Solution:
More concise, but list.contains have the complexity of O(n)
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> results = new ArrayList<>();
if (nums == null) {
return results;
}
dfs(nums, results, new ArrayList());
return results;
}
private void dfs(int[] nums, List<List<Integer>> results, List<Integer> curr) {
if (curr.size() == nums.length) {
results.add(new ArrayList(curr));
}
for (int i : nums) {
if (curr.contains(i)) {
continue;
}
curr.add(i);
dfs(nums, results, curr);
curr.remove(curr.size() - 1);
}
}
}
Using backtracking to find all the permutation. Need to use an array to record the visited type.
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> results = new ArrayList<>();
if (nums == null) {
return results;
}
dfs(nums, results, new ArrayList(), new boolean[nums.length]);
return results;
}
private void dfs(int[] nums, List<List<Integer>> results, List<Integer> curr, boolean[] visited) {
if (curr.size() == nums.length) {
results.add(new ArrayList(curr));
}
for (int i = 0; i < nums.length; i++) {
if (visited[i]) {
continue;
}
visited[i] = true;
curr.add(nums[i]);
dfs(nums, results, curr, visited);
curr.remove(curr.size() - 1);
visited[i] = false;
}
}
}