- #刷题
- #leetcode
Backtracking类型题的经验和攻略整理
xwang13914264
刚开始接触backtracking的时候，感到十分困惑，总觉得看到这种类型的题的时候没有思路。在leetcode上面刷题的时候看到了一个大神分享的模板，针对subset，permutations，和combination sum这几种类型的模板，基础的code其实是非常类似的，但是根据每道题要求不一样，做了一些小细节的变化。我用了这个模板又解了几题，目前可以应用到9道题上面。希望可以给和我一样的小白一些思路。如果大家觉得有用，求一些大米看面经。
以下几点可以每次做题之前先思考一下
3 keys to consider
其实backtracking里面的subset，permutations，和combination sum这几种类型题里面的核心思想就是choose，explore，unchoose
General Idea
[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]
以下几点可以每次做题之前先思考一下
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里面删除掉，这样才不会影响做下一个选择的结果
[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条回复
热度排序
