Description
Given a collection of distinct numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
Solution
DFS
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> permutations = new ArrayList<>();
if (nums == null || nums.length < 1) return permutations;
List<Integer> permutation = new ArrayList<>();
permuteRecur(nums, 0, permutation, permutations);
return permutations;
}
public void permuteRecur(int[] nums
, int begin
, List<Integer> permutation
, List<List<Integer>> permutations) {
if (begin >= nums.length) {
permutations.add(new ArrayList<>(permutation));
return;
}
for (int i = begin; i < nums.length; ++i) {
swap(nums, begin, i);
permutation.add(nums[begin]); // not nums[i]!
permuteRecur(nums, begin + 1, permutation, permutations);
swap(nums, begin, i);
permutation.remove(permutation.size() -1);
}
}
public void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
