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
思路：
(1) 因为是排列问题，所以"for next可能"的时候不从start开始，需要要从0开始并设立used数组以免重复访问
(2) 因为结果要去重，所以需要sort
(3) if(i > 0 && nums[i] == nums[i-1] && !used[i - 1]) continue 来去重。 !used[i - 1] 是来避免 上一次是if(used[i]) continue; 直接出去的而有可能导致的i > 0 && nums[i] == nums[i-1]的corner case，而不是上一轮实际递归作用后了。
Time Complexity: O(N!) Space Complexity: O(N)
Solution Code：
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> cur_res = new ArrayList<>();
Arrays.sort(nums);
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
if(i > 0 && nums[i] == nums[i-1] && !used[i - 1]) continue;
cur_res.add(nums[i]);
used[i] = true;
backtrack(nums, used, cur_res, result);
cur_res.remove(cur_res.size() - 1);
used[i] = false;
}
}
}
