leetcode 46. Permutations（排列）

返回数组nums中数字的所有可能的排列组合。

思路：

排列组合这种一般会想到DFS。

这个排列中每个数字只能用一次，
可用如下DFS流程

stack.push(num);
dfs(nums, num);
stack.pop();

退出条件：
当stack的size和nums数组一样时，说明已经完成了一个排列组合，保存结果退出当前dfs。
否则遍历数组，进入新一轮dfs.

每个数字只能用一次，所以用一个visited数组记录数字是否已经使用过。

class Solution {List<List<Integer>> res = new ArrayList<>();public List<List<Integer>> permute(int[] nums) {Stack<Integer> st = new Stack<>();boolean[] visited = new boolean[nums.length];dfs(nums, st, visited);return res;}void dfs(int[] nums, Stack<Integer> st, boolean[] visited){if(st.size() == nums.length) {List<Integer> list = new ArrayList<>(st);res.add(list);return;}//combinationfor(int i = 0; i < nums.length; i++) {if(visited[i]) continue;st.push(nums[i]);visited[i] = true;dfs(nums, st, visited);st.pop();visited[i] = false;}}
}

也可以不用stack. 直接在nums数组上模拟stack.
把需要装入stack的数字交换到前面，用一个指针模拟栈顶。
此方法更快。

class Solution {List<List<Integer>> res = new ArrayList<>();public List<List<Integer>> permute(int[] nums) {solve(nums, 0);return res;}void solve(int[] nums, int start){if(start == nums.length-1) {List<Integer> list = new ArrayList<>();for(int num : nums) list.add(num);res.add(list);return;}//combinationfor(int i = start; i < nums.length; i++) {swap(nums, start, i);solve(nums, start+1);swap(nums, start, i);}}void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
}