力扣：回溯算法

组合I 

class Solution {
    
    List<List<Integer>> result = new ArrayList(); // 所有结果集
    List<Integer> list = new ArrayList(); // 当前结果集

    public List<List<Integer>> combine(int n, int k) {
        dfs(n, k, 1);
        return result;
    }

    public void dfs(int n, int k, int index) {
        if (list.size() == k) { // 当前结果集等于要收集的数量即可存入最终结果集
            List<Integer> tem = new ArrayList(list);
            result.add(tem);
            return;
        }
        for (int i = index; i <= n; i++) {
            list.add(i); // 元素加入当前结果集
            dfs(n, k, i + 1); // 递归
            list.remove(list.size() - 1); // 该元素组合完成可以移除（回溯）
        }
    }
}

组合II 

class Solution {

    List<List<Integer>> result = new ArrayList(); // 所有结果集
    Set<List<Integer>> set = new HashSet(); // 结果集去重
    List<Integer> list = new ArrayList(); // 当前结果集

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        backTring(candidates, 0, target, 0);
        return result;
    }

    public void backTring(int[] candidates, int sum, int target, int index) {
        if (candidates == null || candidates.length < 0) return; 
        if (sum == target) { // 总和等于目标值是返回当前结果集
            List<Integer> tem = new ArrayList(list);
            Collections.sort(tem); // 去重（如：1 1 2 和 2 1 1 是一组结果集）
            if (!set.contains(tem)) { 
                result.add(new ArrayList(list));
                set.add(tem);
            }
            return;
        }
        if (sum > target) { // 当前结果集大于目标值说明当前结果集不对
            return;
        }
        for (int i = index; i < candidates.length; i++) {
            sum += candidates[i]; // 当前总和
            list.add(candidates[i]); // 当前结果集
            backTring(candidates, sum, target, i + 1);
            sum -= candidates[i]; // 回溯总和
            list.remove(list.size() - 1); // 回溯结果集
        }
    }
}

 组合III

class Solution {

    List<List<Integer>> result = new ArrayList(); // 最终结果集
    List<Integer> list = new ArrayList(); // 当前结果集

    public List<List<Integer>> combinationSum3(int k, int n) {
        backCheck(k, n, 1, 0, 0);
        return result;
    }

    public void backCheck(int k, int n, int num, int count, int sum) {
        if (count == k && n == sum) { // 元素数量等于k 且 sum等于 n 时为符合的结果集
            result.add(new ArrayList(list));
            return;
        }
        if (count > k || n < sum) { // 要求的数量或者总和不对则返回
            return;
        }
        
        for (int i = num; i <= 9; i++) {
            list.add(i);
            sum += i;
            count++;
            backCheck(k, n, i + 1, count, sum);
            list.remove(list.size() - 1);
            sum -= i;
            count--;
        }
    }
}

 分割回文串

class Solution {

    List<List<String>> result = new ArrayList(); // 最终结果集
    List<String> list = new ArrayList(); // 当前结果集

    public String[][] partition(String s) {
        int n = s.length();
        dfs(0, n, s);
        return listToArrays(result); // 集合转换为数组
    }

    public void dfs(int index, int n, String s) {
        if (index == n) { // 指针指向n时说明遍历到字符串末尾，可以返回结果集
            result.add(new ArrayList(list));
            return;
        }
        for (int i = index; i < n; i++) {
            if (isPalindrome(s.substring(index, i + 1))) {  // 如果是回文串则加入当前结果集         
                list.add(s.substring(index, i + 1)); // 加入结果集
                dfs(i + 1, n, s);
                list.remove(list.size() - 1); // 回溯
            }
        }
    }

    public boolean isPalindrome(String str) { // 判断是否为回文串
        int l = 0;
        int r = str.length() - 1;
        while (l < r) {
            if (str.charAt(l) != str.charAt(r)) {
                return false;
            }
            l++;
            r--;
        }
        return true;
    }

    public String[][] listToArrays (List<List<String>> list) { // 集合转换为数组
        int n = list.size();
        String[][] arrs = new String[n][];
        for (int i = 0; i < n; i++) {
            List<String> tem = list.get(i);
            String[] arr = tem.toArray(new String[tem.size()]);
            arrs[i] = arr;
        }
        return arrs;
    }
}

复原 IP 地址

class Solution {

    List<String> res = new ArrayList(); // 所有结果集
    List<String> tem = new ArrayList(); // 当前结果集

    public List<String> restoreIpAddresses(String s) {
        int n = s.length(); // 字符串长度
        if (n < 0 || n > 12) return res; // 剪枝
        dfs(s, 0, n);
        return res;
    }

    public void dfs(String s, int index, int n) {
        if (tem.size() == 4) { // ip地址为四个数字组成，当前结果集等于4即可返回
            if (index == n) { // 当前指针指向末尾即可加入最终结果集
                StringBuilder sb = new StringBuilder(); // 拼凑成需要的字符串
                for (int i = 0; i < 4; i++) {
                    sb.append(tem.get(i));
                    if (i != 3) {
                        sb.append(".");
                    }
                }
                res.add(sb.toString()); // 加入到最终结果集
            }
            return;
        }
        for (int i = index; i < n && i < index + 3; i++) { // 当前指针
            if (isNum(s.substring(index, i + 1))) { //
                tem.add(s.substring(index, i + 1));
                dfs(s, i + 1, n);
                tem.remove(tem.size() - 1);
            }
        }
    }

    public boolean isNum(String s) { // 判断是否为合法数字
        if (s.length() >= 2 && s.charAt(0) == '0') 
            return false;
        Integer num = Integer.valueOf(s);
        if (num > 255) 
            return false;
        return true;
    }
}