Given a collection of numbers, return all possible permutations.
For example,
Solution 1: recursive DFS[1,2,3]
have the following permutations:[1,2,3]
, [1,3,2]
, [2,1,3]
, [2,3,1]
, [3,1,2]
, and [3,2,1]
. public class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res=new ArrayList<>();
dfs(nums,0,res);
return res;
}
private void dfs(int[] nums, int d, List<List<Integer>> res) {
if (d==nums.length){
List<Integer> one=new ArrayList<>();
for (int i=0; i<nums.length; i++) one.add(nums[i]);
res.add(one);
}
else {
dfs(nums,d+1,res);
for (int i=d+1; i<nums.length; i++) {
swap(nums,d,i);
dfs(nums,d+1,res);
swap(nums,d,i);
}
}
}
private void swap(int[] nums, int i, int j) {
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
}
Solution 2: iterative
没有评论:
发表评论