Given a collection of distinct integers, return all possible permutations.
Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
题意：
打印全排列
Solution1: Backtracking
形式化的表示递归过程：permutations(nums[0...n-1]) = {取出一个数字} + permutations(nums[0...n-1] - 该数字)
code
/*
Time: O(n!)
Space: O(n!). We allocate space to keep N! paths.
*/ class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
// corner case
if (nums == null || nums.length == 0) return result;
List<Integer> path = new ArrayList<>();
helper(nums, path, result);
return result;
} private void helper(int[] nums, List<Integer> path, List<List<Integer>> result){
// base case
if(path.size() == nums.length){
result.add(new ArrayList<>(path));
return;
} for(int i = 0; i< nums.length; i++){
if(path.contains(nums[i])) continue;
path.add(nums[i]);
helper(nums, path, result);
path.remove(path.size() - 1);
}
}
}