回溯算法

纯暴力搜索方法

回溯算法其实就是递归算法

组合问题-给一个集合，找出满足条件的组合
切割问题-给一个字符串，切割字符串
子集问题-给一个集合，找出满足条件的子集
排列问题-
棋盘问题-n皇后

组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2：

输入：n = 1, k = 1
输出：[[1]]

代码实例

java

package com.lkcoffee.demo;

import java.util.ArrayList;
import java.util.List;

class Solution {

    private static List<Integer> path;

    private static List<List<Integer>> result;


    public List<List<Integer>> combine(int n, int k) {
        path = new ArrayList<>();
        result = new ArrayList<>();
        getCombine(n, k, 1);
        return result;
    }

    // n为总数，k表示当前是第几层，index表示当前是第几个数。combineList表示当前层已经组合的数
    public void getCombine(int maxN, int maxK, int index) {
        if (path.size() == maxK) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = index; i <= maxN; i++) {
            path.add(i);
            getCombine(maxN, maxK, i + 1);
            path.remove(path.size() - 1);
        }
    }


    public static void main(String[] args) {
        Solution solution = new Solution();
        List<List<Integer>> result = solution.combine(4, 2);
        for (List<Integer> list : result) {
            for (Integer integer : list) {
                System.out.print(integer + " ");
            }
            System.out.println();
        }
    }
}

剪枝操作

基本上都在在

java

for(int i=0;i< size;i++)
{
  
  
}
size中做剪枝

组合总和

216. 组合总和 III

任何一个回溯算法都可以抽象成一个树型结构

java

package com.lkcoffee.demo;

import java.util.ArrayList;
import java.util.List;

class Solution {

    private static List<Integer> path;

    private static List<List<Integer>> result;

    public List<List<Integer>> combinationSum3(int k, int n) {
        path = new ArrayList<>();
        result = new ArrayList<>();
        getCombine(k, n, 1, 0);
        return result;
    }

    // k=表示个数,n表示和.startIndex表示开始位置
    public void getCombine(int k, int n, int startIndex, int sum) {
        // 9- 2+1= 8.  9-1+1 =9
        if (9 - startIndex + path.size() + 1 < k) {
            return;
        }
        //  递归终止条件
        if (path.size() == k) {
            if (sum == n) {
                result.add(new ArrayList<>(path));
            }
            return;
        }
        for (int i = startIndex; i <= 9; i++) {
            path.add(i);
            sum += i;
            if (sum <= n) {
                getCombine(k, n, i + 1, sum);
            }
            path.remove(path.size() - 1);
            sum -= i;
        }
    }


    public static void main(String[] args) {
        Solution solution = new Solution();
        List<List<Integer>> result = solution.combinationSum3(3, 9);
        for (List<Integer> list : result) {
            for (Integer integer : list) {
                System.out.print(integer + " ");
            }
            System.out.println();
        }
    }
}

电话号码的字母组合

https://leetcode.cn/problems/letter-combinations-of-a-phone-number/

java

package com.lkcoffee.demo;

import java.util.ArrayList;
import java.util.List;

class Solution {

    private static final String[] KEY_MAP = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    public List<String> letterCombinations(String digits) {
        List<String> list = new ArrayList<>();
        if (digits.length() == 0) {
            return list;
        }
        backtrack(list, "", digits);
        return list;
    }

    private void backtrack(List<String> list, String combination, String nextDigits) {
        if (nextDigits.length() == 0) {
            list.add(combination);
        } else {
            String letters = KEY_MAP[nextDigits.charAt(0) - '0'];
            for (int i = 0; i < letters.length(); i++) {
                backtrack(list, combination + letters.charAt(i), nextDigits.substring(1));
            }
        }
    }


    public static void main(String[] args) {
        Solution solution = new Solution();
        List<String> list = solution.letterCombinations("23");
        for (String s : list) {
            System.out.println(s);
        }
    }
}

组合总和

https://leetcode.cn/problems/combination-sum/description/

组合总和II

https://leetcode.cn/problems/4sjJUc/

java

package com.lkcoffee.demo;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

class Solution {

    private static List<List<Integer>> result;

    public static List<Integer> path;

    public static List<Boolean> used;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        result = new ArrayList<>();
        path = new ArrayList<>();
        used = new ArrayList<>();
        if (candidates == null || candidates.length == 0) {
            return result;
        }
        Arrays.sort(candidates);
        for(int i = 0; i < candidates.length; i++){
            used.add(false);
        }
        backtracking(candidates, target, 0, 0);
        return result;
    }


    public void backtracking(int[] candidates, int target, int sum, int start) {
        if (sum >= target) {
            if (sum == target) {
                result.add(new ArrayList<>(path));
            }
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if (i > start && candidates[i] == candidates[i - 1] && !used.get(i - 1)) {
                continue;
            }
            path.add(candidates[i]);
            used.set(i, true);
            sum += candidates[i];
            backtracking(candidates, target, sum, i+1);
            path.remove(path.size() - 1);
            used.set(i, false);
            sum -= candidates[i];
        }
    }

    public static void main(String[] args) {
        int[] candidates = {10, 1, 2, 7, 6, 1, 5};
        int target = 8;
        new Solution().combinationSum2(candidates, target);
        for (List<Integer> list : result) {
            for (Integer integer : list) {
                System.out.print(integer + " ");
            }
            System.out.println();
        }
    }
}

分割回文字符串

https://leetcode.cn/problems/M99OJA/description/

这里也是一个回溯算法，需要抽象成一个树形结构

java

    private List<List<String>> result = new ArrayList<>();
    private List<String> path = new ArrayList<>();

    public String[][] partition(String s) {
        if (s == null || s.length() == 0) {
            return new String[0][];
        }
        backTrack(s, 0);
        return result.stream().map(list -> list.toArray(new String[0])).toArray(String[][]::new);
    }

    public boolean isPalindrome(String path) {
        int length = path.length();
        for (int i = 0; i < length; i++) {
            if (path.charAt(i) != path.charAt(length - i - 1)) {
                return false;
            }
        }
        return true;
    }

    public void backTrack(String s, int start) {
        if (start >= s.length()) {
            if (isPalindrome(path.get(path.size() - 1))) {
                result.add(new ArrayList<>(path));
            }
            return;
        }
        for (int i = start; i < s.length(); i++) {
            String substring = s.substring(start, i + 1);
            // 如果是回文
            if (isPalindrome(substring)) {
                path.add(substring);
                backTrack(s, i + 1);
                path.remove(path.size() - 1);
            }
        }
    }

复原IP地址-87

https://leetcode.cn/problems/0on3uN/

java

package com.lkcoffee.demo;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

class Solution {

    private List<List<String>> result = new ArrayList<>();
    private List<String> path = new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {
        backTracking(s, 0, 0);
        return result.stream().map(list -> list.stream().collect(Collectors.joining("."))).collect(Collectors.toList());
    }

    public void backTracking(String s, int startIndex,  int depth) {
        if (depth == 3 ) {
            // 满足条件
            if (isIn255(s.substring(startIndex))) {
                path.add(s.substring(startIndex));
                result.add(new ArrayList<>(path));
                path.remove(path.size() - 1);
            }
            return;
        }

        for(int i = startIndex; i < s.length(); i++){
            if (isIn255(s.substring(startIndex, i + 1))) {
                path.add(s.substring(startIndex, i + 1));
                backTracking(s, i + 1, depth + 1);
                path.remove(path.size() - 1);
            }
        }
    }


    /**
     * 判断是否在255内
     *
     * @param s
     * @return
     */
    public boolean isIn255(String s) {
        if(s.length() ==0 || s.length() > 3){
            return false;
        }
        // 禁止前导0
        if (s.length() > 1 && s.charAt(0) - '0' == 0) {
            return false;
        }
        int num = Integer.parseInt(s);
        return num >= 0 && num <= 255;
    }


    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.restoreIpAddresses("0000"));
    }
}

子集-79

https://leetcode.cn/problems/TVdhkn/description/

java

package com.lkcoffee.demo;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

class Solution {

    private List<List<Integer>> result = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();

    public List<List<Integer>> subsets(int[] nums) {
        backtracking(nums, 0);
        return result;
    }

    private void backtracking(int[] nums, int startIndex){
        result.add(new ArrayList<>(path));
        for (int i = startIndex; i < nums.length; i++) {
            path.add(nums[i]);
            backtracking(nums, i + 1);
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        List<List<Integer>> subsets = solution.subsets(new int[]{1, 2, 3});
        for (List<Integer> subset : subsets){
            System.out.println(subset.stream().map(String::valueOf).collect(Collectors.joining(",")));
        }
    }
}

子集II-90

https://leetcode.cn/problems/subsets-ii/submissions/635645997/

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

回溯算法 ​

组合 ​

剪枝操作 ​

组合总和 ​

电话号码的字母组合 ​

组合总和 ​

分割回文字符串 ​

复原IP地址-87 ​

子集-79 ​

子集II-90 ​

回溯算法

组合

剪枝操作

组合总和

电话号码的字母组合

组合总和

分割回文字符串

复原IP地址-87

子集-79

子集II-90