Backtracking类型题的经验和攻略整理

xwang139

注册一亩三分地论坛，查看更多干货！

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

刚开始接触backtracking的时候，感到十分困惑，总觉得看到这种类型的题的时候没有思路。在leetcode上面刷题的时候看到了一个大神分享的模板，针对subset，permutations，和combination sum这几种类型的模板，基础的code其实是非常类似的，但是根据每道题要求不一样，做了一些小细节的变化。我用了这个模板又解了几题，目前可以应用到9道题上面。希望可以给和我一样的小白一些思路。如果大家觉得有用，求一些大米看面经。

以下几点可以每次做题之前先思考一下
3 keys to consider

Our choice - What choice to make at each call of the function?
Our constraints - When do we stop following a certain path? / When do we not even go one way?
Our goal - What is our target? / Base Case

其实backtracking里面的subset，permutations，和combination sum这几种类型题里面的核心思想就是choose，explore，unchoose

General Idea

Choose // 先做一个选择
Explore // 在这个选择里面探索所有的可能性，call自己
Unchoose // 通常如果我们用list来存结果的话，是需要unchoose，比如把刚才选择的从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]); // Choose
backtrack(list, tempList, nums, i + 1); // Explore
tempList.remove(tempList.size() - 1); // Unchoose
}
}

复制代码

以下是9道leetcode题的写法。基本可以看出来，大致的code和思路是一模一样的，每次只是改了一到两行的写法，或者加了一些小细节。最主要的是需要自己去吃透这些细节的变化，去实际在leetcode上面写几次，之后可以灵活运用。

78. Subsets : https://leetcode.com/problems/subsets/

public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums); // not necessary here
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);
}
}

复制代码

90. Subsets II (contains duplicates) : https://leetcode.com/problems/subsets-ii/

public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums); //skip duplicates
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++){
if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates
tempList.add(nums[i]);
backtrack(list, tempList, nums, i + 1);
tempList.remove(tempList.size() - 1);
}
}

复制代码

46. Permutations : https://leetcode.com/problems/permutations/

public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
// Arrays.sort(nums); // not necessary
backtrack(list, new ArrayList<>(), nums);
return list;
}
private 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; // element already exists, skip
tempList.add(nums[i]);
backtrack(list, tempList, nums);
tempList.remove(tempList.size() - 1);
}
}
}

复制代码

47. Permutations II (contains duplicates) : https://leetcode.com/problems/permutations-ii/

public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
backtrack(list, new ArrayList<>(), nums, new boolean[nums.length]);
return list;
}
private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, boolean [] used){
if(tempList.size() == nums.length){
list.add(new ArrayList<>(tempList));
} else{
for(int i = 0; i < nums.length; i++){
if(used[i] || i > 0 && nums[i] == nums[i-1] && !used[i - 1]) continue;
used[i] = true;
tempList.add(nums[i]);
backtrack(list, tempList, nums, used);
used[i] = false;
tempList.remove(tempList.size() - 1);
}
}
}

复制代码

77. Combinations :
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> list = new ArrayList<>();
backtrack(list, new ArrayList(), n, k, 1);
return list;
}
private void backtrack(List<List<Integer>> list, List<Integer> sublist, int n, int k, int start) {
if(sublist.size() == k) {
list.add(new ArrayList<>(sublist));
} else {
for(int i = start; i <= n; i++) {
if(sublist.contains(i)) {
continue;
}
sublist.add(i);
backtrack(list, sublist, n, k, i + 1);
sublist.remove(sublist.size() - 1);
}
}
}

复制代码

39. Combination Sum : https://leetcode.com/problems/combination-sum/

public List<List<Integer>> combinationSum(int[] nums, int target) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
backtrack(list, new ArrayList<>(), nums, target, 0);
return list;
}
private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
if(remain < 0) return;
else if(remain == 0) list.add(new ArrayList<>(tempList));
else{
for(int i = start; i < nums.length; i++){
tempList.add(nums[i]);
backtrack(list, tempList, nums, remain - nums[i], i); // not i + 1 because we can reuse same elements
tempList.remove(tempList.size() - 1);
}
}
}

复制代码

40. Combination Sum II (can't reuse same element) : https://leetcode.com/problems/combination-sum-ii/

public List<List<Integer>> combinationSum2(int[] nums, int target) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
backtrack(list, new ArrayList<>(), nums, target, 0);
return list;
}
private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
if(remain < 0) return;
else if(remain == 0) list.add(new ArrayList<>(tempList));
else{
for(int i = start; i < nums.length; i++){
if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates
tempList.add(nums[i]);
backtrack(list, tempList, nums, remain - nums[i], i + 1);
tempList.remove(tempList.size() - 1);
}
}
}

复制代码

216. Combination Sum III (unique set of numbers && combination of k numbers add to n, and the range is 1 to 9) : https://leetcode.com/problems/combination-sum-iii/

public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> list = new ArrayList<>();
backtrack(k, n, list, new ArrayList(), 1);
return list;
}
private void backtrack(int k, int n, List<List<Integer>> list, List<Integer> sublist, int start) {
if(n < 0 || sublist.size() > k) {
return;
} else if(sublist.size() == k && n == 0) {
list.add(new ArrayList<>(sublist));
} else {
for(int i = start; i <= 9; i++) {
sublist.add(i);
backtrack(k, n - i, list, sublist, i + 1);
sublist.remove(sublist.size() - 1);
}
}
}

复制代码

131. Palindrome Partitioning : https://leetcode.com/problems/palindrome-partitioning/

public List<List<String>> partition(String s) {
List<List<String>> list = new ArrayList<>();
backtrack(list, new ArrayList<>(), s, 0);
return list;
}
public void backtrack(List<List<String>> list, List<String> tempList, String s, int start){
if(start == s.length())
list.add(new ArrayList<>(tempList));
else{
for(int i = start; i < s.length(); i++){
if(isPalindrome(s, start, i)){
tempList.add(s.substring(start, i + 1));
backtrack(list, tempList, s, i + 1);
tempList.remove(tempList.size() - 1);
}
}
}
}
public boolean isPalindrome(String s, int low, int high){
while(low < high)
if(s.charAt(low++) != s.charAt(high--)) return false;
return true;
}

复制代码

akdhfikbk

为啥backtracking的攻略这么多...

补充内容 (2020-2-12 08:18):
补充下，这不就是lc原贴吗？https://leetcode.com/problems/su ... -questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partitioning)

xwang139

akdhfikbk 发表于 2020/02/03 12:10:04
为啥backtracking的攻略这么多...

补充内容 (2020-2-12 08:18):
补充下，这不就是lc原...

是的，我上面写了来源，原帖大概有5题，我又加了几题。第一段都有写。

补充内容 (2020-2-12 09:36):
这算是一个整理贴，前面加了一些想法，后面加了一些可以用这个模版写的题，如果不符合规定，就请管理员把这个帖子移除吧。

yeetatbig4

谢谢整理到一起，只做过前4道

mikezy

我的理解是：
//压栈
//backtracking/dfs
//出栈

仅供参考

xwang139

mikezy 发表于 2020/02/13 16:02:34
我的理解是：
//压栈
//backtracking/dfs
//出栈

仅供参考

栈应该是说stack，不过bracktrack的这个模版和栈应该没什么关系。或者你指的是add 和 remove的部分。这些类型的题一般要返回的最终结果是List<List<Integer>>，因为我们一直在用list来记录每一次的选择，然后dfs把这个list传进去，由于java里面list是pass by reference，所以指的还是原来这个list，对原来list进行的操作都会保存下来。所以每次返回上一层去探索另一种可能性之前需要remove刚才的选择。但是如果最后要的结果是一个数字或者string，而不是一个list，就不用add 和 remove，因为int 和 string在每次重新pass进dfs的时候是copy of a value。目前写法都是没有return值，而是pass in。所以下面一层对数字和string的操作并不会影响上一层。

欢迎讨论，这也只是我的理解，还是刷题路上的小白一枚。

[Leetcode] Backtracking类型题的经验和攻略整理

注册一亩三分地论坛，查看更多干货！

评分

浏览过的版块