登录
  • #刷题
  • #leetcode

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

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

以下几点可以每次做题之前先思考一下

3 keys to consider



  1. Our choice - What choice to make at each call of the function?

  2. Our constraints - When do we stop following a certain path? / When do we not even go one way?

  3. 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里面删除掉,这样才不会影响做下一个选择的结果



[mw_shl_code=java,true]private void backtrack(List<List<Integer>> list , List<Integer> tempList, int [] nums, int start){[br]
list.add(new ArrayList<>(tempList));

for(int i = start; i < nums.length; i++){

tempList.add(nums); // Choose

backtrack(list, tempList, nums, i + 1); // Explore

tempList.remove(tempList.size() - 1); // Unchoose

}

}

[/mw_shl_code]

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

78. Subsets : leetcode.com

[mw_shl_code=java,true]public List<List<Integer>> subsets(int[] nums) {[br]
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){[br]
list.add(new ArrayList<>(tempList));

for(int i = start; i < nums.length; i++){

tempList.add(nums);

backtrack(list, tempList, nums, i + 1);

tempList.remove(tempList.size() - 1);

}

}

[/mw_shl_code]

90. Subsets II (contains duplicates) : leetcode.com

[mw_shl_code=java,true]public List<List<Integer>> subsetsWithDup(int[] nums) {[br]
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){[br]
list.add(new ArrayList<>(tempList));

for(int i = start; i < nums.length; i++){

if(i > start && nums == nums[i-1]) continue; // skip duplicates

tempList.add(nums);

backtrack(list, tempList, nums, i + 1);

tempList.remove(tempList.size() - 1);

}

}

[/mw_shl_code]

46. Permutations : leetcode.com

[mw_shl_code=java,true]public List<List<Integer>> permute(int[] nums) {[br]
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){[br]
if(tempList.size() == nums.length){

list.add(new ArrayList<>(tempList));

} else{

for(int i = 0; i < nums.length; i++){

if(tempList.contains(nums)) continue; // element already exists, skip

tempList.add(nums);

backtrack(list, tempList, nums);

tempList.remove(tempList.size() - 1);

}

}

}

[/mw_shl_code]

47. Permutations II (contains duplicates) : leetcode.com

[mw_shl_code=java,true]public List<List<Integer>> permuteUnique(int[] nums) {[br]
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 > 0 && nums == nums[i-1] && !used) continue;

used = true;

tempList.add(nums);

backtrack(list, tempList, nums, used);

used = false;

tempList.remove(tempList.size() - 1);

}

}

}

[/mw_shl_code]

77. Combinations :

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

[mw_shl_code=bash,true]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);

}

}

}

[/mw_shl_code]

39. Combination Sum : leetcode.com

[mw_shl_code=java,true]public List<List<Integer>> combinationSum(int[] nums, int target) {[br]
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){[br]
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);

backtrack(list, tempList, nums, remain - nums, i); // not i + 1 because we can reuse same elements

tempList.remove(tempList.size() - 1);

}

}

}

[/mw_shl_code]

40. Combination Sum II (can't reuse same element) : leetcode.com

[mw_shl_code=java,true]public List<List<Integer>> combinationSum2(int[] nums, int target) {[br]
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){[br]
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 == nums[i-1]) continue; // skip duplicates

tempList.add(nums);

backtrack(list, tempList, nums, remain - nums, i + 1);

tempList.remove(tempList.size() - 1);

}

}

}

[/mw_shl_code]

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

[mw_shl_code=java,true] 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);

}

}

}

[/mw_shl_code]

131. Palindrome Partitioning : leetcode.com

[mw_shl_code=java,true]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;

}

[/mw_shl_code]
4条回复
热度排序

发表回复