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：Backtracking
总结见：http://www.jianshu.com/p/883fdda93a66
思路：
backtracking的基本套路，要注意的是：
因为是排列问题，所以"for next可能"的时候不从start开始，需要要从0开始并设立used数组以免重复访问
Time Complexity: O(N!) Space Complexity: O(N)
Solution Code：
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> cur_res = new ArrayList<>();
// Arrays.sort(nums); // not necessary
boolean[] used = new boolean[nums.length];
backtrack(nums, used, cur_res, result);
return result;
}
private void backtrack(int[] nums, boolean[] used, List<Integer> cur_res, List<List<Integer>> result) {
if(cur_res.size() == nums.length){
result.add(new ArrayList<>(cur_res));
return;
}
for(int i = 0; i < nums.length; i++){
if(used[i]) continue; // element already exists, skip
cur_res.add(nums[i]);
used[i] = true;
backtrack(nums, used, cur_res, result);
cur_res.remove(cur_res.size() - 1);
used[i] = false;
}
}
}
