博文中会简要介绍Leetcode P0046题目分析及解题思路。
“Permutations”是一道比较基础的深度优先搜索的题目，也就是回溯法。对于这样的问题，可以通过排序来去重，然后使用DFS得到结果。
Given a collection of distinct integers, return all possible permutations.
Example:
Input: [1,2,3] Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
以下是Java的题解代码实现。
class Solution {
public List<List<Integer>> permute(int[] nums) {
if (nums == null || nums.length == 0)
return this.permutations;
this.dfs(nums, new ArrayList<>(), new boolean[nums.length], 0);
return this.permutations;
}
private List<List<Integer>> permutations = new ArrayList<>();
private void dfs(int[] nums, List<Integer> sequence, boolean[] used, int count) {
if (count >= nums.length) {
List<Integer> copied = new ArrayList<>(sequence);
permutations.add(copied);
return;
}
for (int itr=0; itr<nums.length; ++itr) {
if (used[itr])
continue;
sequence.add(nums[itr]);
used[itr] = true;
this.dfs(nums, sequence, used, count+1);
used[itr] = false;
sequence.remove(sequence.size()-1);
}
}
}