LeetCode Q46 Permutations

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution
{
public List<List<Integer>> permute(int[] nums)
{
List<List<Integer>> list = new ArrayList<>();
backtrack(list, new ArrayList<>(), nums);
return list;
}

public void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums)
{
if(tempList.size() == nums.length)
{
list.add(new ArrayList<>(tempList));
}
else
{
for(int i = 0; i < nums.length; i++)
{
//跳过已经存在的元素
if(tempList.contains(nums[i])) continue;
//将当前元素加入
tempList.add(nums[i]);
//向后继续添加
backtrack(list, tempList, nums);
//将 tempList 刚添加的元素,去掉,尝试新的元素
//每次超出for loop的循环或者size == nums.length时都会运行此行,so called backtrack
tempList.remove(tempList.size() - 1);
}
}
}

}