LeetCode 46. Permutations

https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-xiang-jie-by-labuladong-2/

这里值得注意的是List有contains()方法可用。

class Solution { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> res = new ArrayList<>(); backtrack(nums, new ArrayList<>(), res); return res; } private void backtrack(int[] nums, List<Integer> path, List<List<Integer>> res){ if(path.size() == nums.length){ res.add(new ArrayList<>(path)); return; } for(int i = 0; i < nums.length; i++){ if(path.contains(nums[i])){ continue; } path.add(nums[i]); backtrack(nums, path, res); path.remove(path.size() - 1); } } }

当然，也可以维护一个boolean数组used，使用过一个数以后，就把对应的boolean元素设为true。

class Solution { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> res = new ArrayList<>(); backtrack(nums, new boolean[nums.length], new ArrayList<>(), res); return res; } private void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res){ if(path.size() == nums.length){ res.add(new ArrayList<>(path)); return; } for(int i = 0; i < nums.length; i++){ if(used[i]){ continue; } path.add(nums[i]); used[i] = true; backtrack(nums, used, path, res); path.remove(path.size() - 1); used[i] = false; } } }