利用回溯算法解决的几道题

回溯算法模板：

result = [];
def backtrack(路径，选择列表)
    if 满足条件：
        result.add(路径)
        return
    for 选择 in 选择列表：
        做选择
        backtrack(路径，选择列表)
        撤销选择

它可以解决子集，组合和排序问题。

这道题归属于组合问题，只要不重复就行，不在意顺序。
直接看这道题的代码：

import java.util.*;
public class Solution {
    ArrayList<ArrayList<Integer>> res = new ArrayList<>(); 
    public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
        Arrays.sort(num);
        ArrayList<Integer> temp = new ArrayList<>();
        backtrack(num, target, temp, 0);
        return res;
    }

    public void backtrack(int[] num, int target, ArrayList<Integer> temp, int start){
        //如果等于目标数，就添加进结果集
        if(target == 0){
            res.add(new ArrayList<Integer>(temp));
            return;
        }
        for(int i = start; i < num.length; i++){
            //去重 同一层用过的num[i]不可以再用，不然会出现一样的组合
            //可以画一个决策树看一下
            if(i > start && num[i] == num[i-1]) continue;    
            if(num[i] <= target){    //剪枝 不剪枝会超时
                temp.add(num[i]);
                backtrack(num, target-num[i], temp, i+1);
                temp.remove(temp.size()-1);
            }

        }
        return;
    }
}

start参数用来控制递归，相当于保证决策树的每一层递归下去。而在选择列表里i的选择相当于决策树每一层的选择，每一层递归时都从start开始，保证没有重复项。
这里需要注意去重和剪枝。
去重是符合题目不能有相同的组合，剪枝是为了避免没必要的递归，避免超时。

再来看直接求组合的问题：

因为选择列表是没有重复项的，因此不需要去重。
代码实现：

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        List<Integer> temp = new ArrayList<>();
        backtrack(temp, n, k, 1);
        return res;
    }

    public void backtrack(List<Integer> temp, int n, int k, int start){
        if(temp.size() == k){
            res.add(new ArrayList<Integer>(temp));
            return;
        }
        for(int i = start; i <= n; i++){
            temp.add(i);
            backtrack(temp, n, k, i+1);
            temp.remove(temp.size()-1);
        }
        return;
    }
}

接下来看子集问题：

我们也可以画出决策树，以[1,2,3]为例：

代码实现：

public class Solution {
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> subsets(int[] S) {
        ArrayList<Integer> temp = new ArrayList<>();
        backtrack(S, temp, 0);
        return res;
    }

    public void backtrack(int[] S, ArrayList<Integer> temp, int start){
        res.add(new ArrayList<Integer>(temp));

        for(int i = start; i < S.length; i++){
            temp.add(S[i]);
            backtrack(S, temp, i+1);
            temp.remove(temp.size()-1);
        }
    }
}

再来看排序问题：

这个不需要start参数来防止出现重复项，只需要每次通过contains()方法来排除在track中选过的数字。
代码实现：

import java.util.*;
public class Solution {
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<Integer> temp = new ArrayList<>();
        backtrack(num, temp);
        return res;
    }

    void backtrack(int[] num, ArrayList<Integer> temp){
        if(temp.size() == num.length){
            res.add(new ArrayList<Integer>(temp));
            return;
        }
        for(int i = 0; i < num.length; i++){
            if(temp.contains(num[i]))
                continue;
            temp.add(num[i]);
            backtrack(num, temp);
            temp.remove(temp.size()-1);
        }
        return;
    }
}

可以利用标记数字，在遇到重复数字时，

import java.util.*;

public class Solution {
    boolean[] mark;
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        ArrayList<Integer> track = new ArrayList<>();
        mark = new boolean[num.length];
        Arrays.sort(num);
        backtrack(num, res, track);
        return res;
    }

    public void backtrack(int[] num, ArrayList<ArrayList<Integer>> res, ArrayList<Integer> track){
        if(track.size() == num.length){
            res.add(new ArrayList<>(track));
            return;
        }
        for(int i = 0; i < num.length; i++){
            if(mark[i] || i > 0 && num[i] == num[i-1] && !mark[i-1]) //&&的优先级要高于||
                continue;
            track.add(num[i]);
            //标记为已访问
            mark[i] = true;
            backtrack(num, res, track);
            track.remove(track.size()-1);
            //标记为未访问
            mark[i] = false;
        }
        return;
    }
}

将数字字符串转化为ip地址

用回溯框架来做：

public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return string字符串ArrayList
     */
    ArrayList<String> res;
    public ArrayList<String> restoreIpAddresses (String s) {
        // write code here
        res = new ArrayList<String>();
        if(s.length() == 0) return res;
        backtrack(s, 0, 3);
        return res;
    }
    //i表示本次插入的起始位置 cnt表示可插入`.`的次数
    public void backtrack(String s, int i, int cnt){
        //终止条件
        if(cnt == 0){
            String[] strs = s.split("\\.");
            if(strs.length < 4) return;
            for(String str : strs){
                if(str.length() > 1 && str.charAt(0) == '0') return;
                if(Integer.parseInt(str) < 0 || Integer.parseInt(str) > 255) return;
            }
            //排除完一系列不合格后 再添加
            res.add(s);
            return;
        }

        if(i >= s.length()) return; //没有插完全部的点，就已经超出范围了。
        int n = s.length();
        backtrack(s.substring(0,i+1)+"."+s.substring(i+1,n), i+2, cnt-1);//每次将一个字符作为一位
        ////相当于撤销，每次将2个字符作为一位
        if(i+2 < n) backtrack(s.substring(0,i+2)+"."+s.substring(i+2,n), i+3, cnt-1);
        //相当于撤销，每次将3个字符作为一位
        if(i+3<n)backtrack(s.substring(0,i+3)+"."+s.substring(i+3,n), i+4, cnt-1);

    }
}

关于括号生成有两个性质：

• 一个合法括号组合的左括号数量一定等于右括号数量
• 对于任何0 <= i < len都有：子串[0...i]中的左括号数量等于右括号数量

C++版：

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @return string字符串vector
     */
    vector<string> generateParenthesis(int n) {
        // write code here
        if(n == 0) return {};
        vector<string> res;
        string track;
        backtrack(n, n, res, track);
        return res;
    }
    void backtrack(int left, int right, vector<string>& res, string& track){
        if(left < 0 || right < 0)
            return;
        if(right < left)
            return;
        if(left == 0 && right == 0){
            res.push_back(track);
            return;
        }

        track.push_back('(');
        backtrack(left-1, right, res, track);
        track.pop_back();

        track.push_back(')');
        backtrack(left, right-1, res, track);
        track.pop_back();
    }
};

Java版：

public class Solution {
    /**
     * 
     * @param n int整型 
     * @return string字符串ArrayList
     */
    ArrayList<String> res;
    public ArrayList<String> generateParenthesis (int n) {
        // write code here
        res = new ArrayList<>();
        String track = new String();
        backtrack(n, n, track);
        return res;
    }

    public void backtrack(int left, int right, String track){
        if(left < 0 || right < 0)
            return;
        if(right < left)
            return;
        if(left == 0 && right == 0)
            res.add(track);

        track = track+"(";
        backtrack(left-1, right, track);
        track = track.substring(0, track.length()-1);

        track = track+")";
        backtrack(left, right-1, track);
        track = track.substring(0, track.length()-1);
    }
}

或者：

public class Solution {
    /**
     * 
     * @param n int整型 
     * @return string字符串ArrayList
     */
    ArrayList<String> res;
    public ArrayList<String> generateParenthesis (int n) {
        // write code here
        res = new ArrayList<>();
        String track = new String();
        backtrack(n, n, track);
        return res;
    }

    public void backtrack(int left, int right, String track){
        //
        if(left == 0 && right == 0){
            res.add(track);
            return;
        }
        //当left还剩    
        if(left > 0){
            backtrack(left-1, right, track+"(");
        }
        //当右括号剩得还比左括号多
        if(right > left){
            backtrack(left, right-1, track+")");
        }

    }
}