第13章 回溯法

组合问题

剑指offerⅡ79：所有子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

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

写法一：

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new LinkedList<>();
        if(nums.length==0){
            return ans;
        }
        dfs(nums,0,new LinkedList<>(),ans);
        System.out.println(ans.toString());
        return ans;
    }

    private void dfs(int[] nums, int index, LinkedList<Integer> subset, List<List<Integer>> ans){
        if(index==nums.length){
            ans.add(new LinkedList<>(subset));
            return;
        }
        subset.add(nums[index]);		//先选择下标为index的数
        dfs(nums,index+1, subset, ans); //在选择index的情况下，确定index+1的选择情况
        subset.removeLast();			//不选择下标为index的数
        dfs(nums,index+1, subset, ans); //在不选择index的情况下，确定index+1的选择情况
    }
}

剑指offerⅡ80：包含k个元素的组合

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> ans = new LinkedList<>();
        LinkedList<Integer> combination = new LinkedList<>();
        dfs(1, n,k, ans, combination);
        return ans;
    }

    private void dfs(int i, int n, int k, List<List<Integer>> ans, LinkedList<Integer> combination){
        if(combination.size()==k){
            ans.add(new LinkedList<>(combination));
            return;
        }
        if(i <= n){
            combination.add(i);
            dfs(i+1, n,k, ans, combination);
            combination.removeLast();
            dfs(i+1, n,k, ans, combination);
        }
    }
}

剑指offerⅡ81：允许重复选择元素的组合

给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。

candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。

对于给定的输入，保证和为 target 的唯一组合数少于 150 个。

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new LinkedList<>();
        LinkedList<Integer> combination = new LinkedList<>();
        Arrays.sort(candidates);
        dfs(target, 0, candidates, combination, ans);
        return ans;
    }

    private void dfs(int target, int i, int[] nums, LinkedList<Integer> combination, List<List<Integer>> ans) {
        if (target == 0) {
            ans.add(new LinkedList<>(combination));
            return;
        }
        if (target > 0 && i < nums.length) {
//            if(nums[i] > target){
//                return;
//            }
            combination.add(nums[i]);//加入nums[i]
            dfs(target - nums[i], i, nums, combination, ans);//判断是否可以继续加入nums[i]
            combination.removeLast();//对于该层而言（这一点很重要，需要理解），删除一个nums[i]，相当于不将nums[i]加入其中
            dfs(target, i + 1, nums, combination, ans);//那么要判断是否可以加入nums[i+1]
        }
    }
}

二刷遇到的问题：

• LinkedList才有removeLast方法
• 先排序，再剪枝，优化时间复杂度

上面的代码执行耗时:4 ms,击败了36.75% 的Java用户；内存消耗:39.1 MB,击败了5.70% 的Java用户。所以需要剪枝提速，又因为candidates里面都是正整数，所以可以在if(target > 0 && i < nums.length)中加入剪枝：if(candidates[i] > target){return;}

剑指offerⅡ82：包含重复元素的组合

给定一个可能有重复数字的整数数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次，解集不能包含重复的组合。

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> ans = new LinkedList<>();
        LinkedList<Integer> combination = new LinkedList<>();
        Arrays.sort(candidates);
        dfs(0, target, candidates, ans, combination);
        return ans;
    }

    private void dfs(int i, int target, int[] nums, List<List<Integer>> ans, LinkedList<Integer> combination){
        if(target==0){
            ans.add(new LinkedList<>(combination));
            return;
        }
        if(i<nums.length && target>0){
            combination.add(nums[i]);
            dfs(i+1,target-nums[i],nums,ans, combination);
            combination.removeLast();
            dfs(findNext(i, nums),target,nums, ans, combination);
        }
    }

    private int findNext(int i, int[] nums){
        int next = i;
        while(next<nums.length && nums[i]==nums[next]){
            next++;
        }
        return next;
    }
}

LC17：电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

代码：

class Solution {
    List<String> combinitions = new ArrayList<>();

    public List<String> letterCombinations(String digits) {
        if (digits.length() == 0) {
            return combinitions;
        }
        Map<Character, String> num2letters = new HashMap<>() {{
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};
        dfs(0, digits, combinitions, new StringBuilder(), num2letters);
        return combinitions;
    }

    private void dfs(int index, String digits, List<String> combinitions, StringBuilder combinition, Map<Character, String> num2letters) {
        if (index == digits.length()) {
            combinitions.add(combinition.toString());
            return;
        }
        char digit = digits.charAt(index);
        String letters2beSelected = num2letters.get(digit);
        int lengthOfString = letters2beSelected.length();
        for (int i = 0; i < lengthOfString; i++) {
            combinition.append(letters2beSelected.charAt(i));
            dfs(index + 1, digits, combinitions, combinition, num2letters);
            combinition.deleteCharAt(index);
        }
    }
}

排列问题

剑指offerⅡ83：没有重复元素集合的全排列

给定一个不含重复数字的整数数组 nums ，返回其 所有可能的全排列 。可以 按任意顺序 返回答案。

经典解法：

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new LinkedList<>();
        LinkedList<Integer> permutation = new LinkedList<>();
        dfs(0,nums,ans,permutation);
        return ans;
    }
	
    //确定位置i的数字
    private void dfs(int i, int[] nums, List<List<Integer>> ans, LinkedList<Integer> permutation){
        if(i==nums.length){
            permutation.clear();
            for(int num:nums){
                permutation.add(num);
            }
            ans.add(new LinkedList<>(permutation));
            return;
        }
        if(i<nums.length){
            for (int j=i;j<nums.length;j++){//循环确定位置i的数字，遍历所有可能
                swap(nums, i, j);
                dfs(i+1,nums,ans,permutation);
                swap(nums, i, j);
            }
        }
    }

    private void swap(int[] nums, int i, int j){
        if(i!=j){
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
}

比较容易理解的解法：

剑指offerⅡ84：包含重复元素集合的全排列

给定一个可包含重复数字的整数集合 nums ，按任意顺序 返回它所有不重复的全排列。

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new LinkedList<>();
        LinkedList<Integer> permutation = new LinkedList<>();
        dfs(nums, 0, ans, permutation);
        return ans;
    }

    private void dfs(int[] nums, int i, List<List<Integer>> ans, LinkedList<Integer> permutation){
        if(i==nums.length){
            permutation = new LinkedList<>();
            for(int num:nums){
                permutation.add(num);
            }
            ans.add(permutation);
            return;
        }
        Set<Integer> set = new HashSet<>();
        for (int j=i;j<nums.length;j++){
            if(!set.contains(nums[j])) {
                set.add(nums[j]);//记录所有和nums[i]交换过的数字，如果再次遇到相同的数字，则跳过
                swap(nums, i, j);
                dfs(nums, i + 1, ans, permutation);
                swap(nums, i, j);
            }
        }
    }

    private void swap(int[] nums, int i, int j){
        if(i!=j){
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
}

用set来记录所有和nums[i]交换过的数字，如果发现有相同的数字已经被交换过了，则直接跳过该数字。

剑指offerⅡ85：生成匹配的括号

正整数 n 代表生成括号的对数，请设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 ：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

思路：

• 左括号或右括号的数目不能超过n个
• 任意步骤中，已经生成的右括号数目不能超过左括号数目
• 如果在上一步所有括号已经匹配，下一个括号只能是左括号

本书代码：

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new LinkedList<>();
        dfs(n, n, "", ans);
        return ans;
    }

    private void dfs(int left, int right, String s, List<String> ans){
        if(left == 0 && right == 0){
            ans.add(s);
            return;
        }
        if(left > 0){
            dfs(left - 1, right, s + "(", ans);
        }
        if(left < right){
            dfs(left, right - 1, s + ")", ans);
        }
    }
}

自己写的代码：

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new LinkedList<>();
        generate(0, 0, ans, new String(), n);
        return ans;
    }

    private void generate(int left, int right, List<String> ans, String thesis, int n) {
        if (left == n && right == n) {
            ans.add(new String(thesis));
            return;
        }
        if (left < n) {
            generate(left + 1, right, ans, thesis + "(", n);
        }
        if (left > right) {
            generate(left, right + 1, ans, thesis + ")", n);
        }
    }
}

在这个题目中，String作为包装类型，传入函数中被修改后，跳出函数中仍然是原来的值，这跟基本数据类型的表现一样，为什么会这样？可以从JVM的角度去解释。

剑指offerⅡ86：分割回文子字符串

给定一个字符串 s ，请将 s 分割成一些子串，使每个子串都是 回文串 ，返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例 1：

输入：s = "google"
输出：[["g","o","o","g","l","e"],["g","oo","g","l","e"],["goog","l","e"]]

示例 2：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 3：

输入：s = "a"
输出：[["a"] 

提示：

• 1 <= s.length <= 16
• s 仅由小写英文字母组成

书本的代码：

class Solution {
    public String[][] partition(String s) {
        List<String[]> res = new LinkedList<>();
        dfs(res, new LinkedList<>(), 0, s);
        return res.toArray(new String[res.size()][]);
    }

    private void dfs(List<String[]> res, LinkedList<String> substrings, int start, String s){
        if(start == s.length()){
            res.add(substrings.toArray(new String[substrings.size()]));
            return;
        }
        for(int end=start;end<s.length();end++){
            if(isPalindrome(start,end,s)){
                substrings.add(s.substring(start, end+1));
                dfs(res,substrings,end+1,s);
                substrings.removeLast();
            }
        }
    }

    private boolean isPalindrome(int left, int right, String str){
        while(left<right){
            if(str.charAt(left++)!=str.charAt(right--)){
                return false;
            }
        }
        return true;
    }
}

剑指offerⅡ87：恢复IP地址

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和"192.168@1.1" 是 无效 IP 地址。

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

输入：s = "1111"
输出：["1.1.1.1"]

示例 4：

输入：s = "010010"
输出：["0.10.0.10","0.100.1.0"]

示例 5：

输入：s = "10203040"
输出：["10.20.30.40","102.0.30.40","10.203.0.40"]

书上的代码：

class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> result = new LinkedList<>();
        dfs(s, 0, 0, "", "", result );
        return result;
    }

    private void dfs(String s, int i, int segI, String seg, String ip, List<String> result){
        if(i==s.length() && segI==3 && isValieSeg(seg)){
            result.add(ip+seg);
            return;
        }
        if(i<s.length()){
            char ch = s.charAt(i);
            if(isValieSeg(seg+ch)){
                dfs(s, i+1, segI, seg+ch, ip, result);
            }
            if(seg.length()>0 && segI<3){
                dfs(s, i+1, segI+1, ""+ch, ip+seg+".", result);
            }
        }
    }

    private boolean isValieSeg(String seg){
        return Integer.valueOf(seg)<=255 && (seg.charAt(0)!='0'||seg.equals("0"));
    }
}