每天发一道 leetcode 题目，最近发现 A 的回溯题目有点多，基本就用一个模板搞定。

• [ Leetcode ] 77. 组合
• [ Leetcode ] 60. 第 k 个排列
• [ Leetcode ] 47. 全排列 II
• [ Leetcode ] 46.全排列

[ Leetcode ] 79. 子集

java

class Solution { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> list = new ArrayList<>(); Arrays.sort(nums); backtrack(list, new ArrayList<>(), nums, 0); return list; } private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums, int start) { list.add(new ArrayList<>(tempList)); for (int i = start; i < nums.length; i++) { tempList.add(nums[i]); backtrack(list, tempList, nums, i + 1); tempList.remove(tempList.size() - 1); } } } 

python

class Solution: def subsets(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ list = [] nums.sort() self.bracktrack(list, [], nums, 0) return list def bracktrack(self, list, tempList, nums, start): list.append(tempList.copy()) for i in range(start, len(nums)): tempList.append(nums[i]) self.bracktrack(list, tempList, nums, i + 1) tempList.pop() 

[ Leetcode ] 77. 组合

java 版本

class Solution { public List<List<Integer>> combine(int n, int k) { List<List<Integer>> res = new ArrayList<>(); backtrack(res, n, 1, k, new ArrayList<>()); return res; } public void backtrack(List<List<Integer>> res, int n, int num, int k, List<Integer> list) { if (list.size() == k) { res.add(new ArrayList<>(list)); } else { for (int i = num; i <= n; i++) { list.add(i); backtrack(res, n, i + 1, k, list); list.remove(list.size() - 1); } } } } 

python 版本

class Solution: def backtrack(self, res, n, nums, k, current): if len(current) == k: res.append(current.copy()) else: for i in range(nums, n + 1): current.append(i) self.backtrack(res, n, i + 1, k, current) current.pop() def combine(self, n, k): """ :type n: int :type k: int :rtype: List[List[int]] """ res = [] self.backtrack(res, n, 1, k, []) return res 

[ Leetcode ] 46.全排列

class Solution { public static List<List<Integer>> permute(int[] nums) { List<List<Integer>> res = new ArrayList<>(); backtrack(res, new ArrayList<>(), nums); return res; } public static void backtrack(List<List<Integer>> res, List<Integer> tempRes, int[] nums) { if (tempRes.size() == nums.length) { //遍历完了,不需要回溯了. res.add(new ArrayList<>(tempRes)); } else { for (int i = 0; i < nums.length; i++) { if (tempRes.contains(nums[i])) { //System.out.println("i:" + i + "---" + tempRes.stream().map(String::valueOf).collect(Collectors.joining(","))); continue; } tempRes.add(nums[i]); //System.out.println("i:" + i + "---" + tempRes.stream().map(String::valueOf).collect(Collectors.joining(","))); backtrack(res, tempRes, nums); tempRes.remove(tempRes.size() - 1); //System.out.println("i:" + i + ":afterRemoveLast---" + tempRes.stream().map(String::valueOf).collect(Collectors.joining(","))); } } } } 

[ Leetcode ] 47. 全排列 II

class Solution { public static List<List<Integer>> permuteUnique(int[] nums) { List<List<Integer>> res = new ArrayList<>(); Arrays.sort(nums); boolean[] used = new boolean[nums.length]; backtrack(res, new ArrayList<>(), nums, used); return res; } public static void backtrack(List<List<Integer>> res, List<Integer> tempRes, int[] nums, boolean[] used) { if (tempRes.size() == nums.length) { //遍历完了,不需要回溯了. res.add(new ArrayList<>(tempRes)); } else { for (int i = 0; i < nums.length; i++) { if (used[i]) { continue; } if (i > 0 && nums[i - 1] == nums[i] && !used[i - 1]) { continue; } used[i] = true; tempRes.add(nums[i]); backtrack(res, tempRes, nums, used); used[i] = false; tempRes.remove(tempRes.size() - 1); } } } }