算法第二十二天|回溯

39. 组合总和

public class Solution {

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

    LinkedList<Integer> list = new LinkedList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if (candidates.length <= 0) {
            return result;
        }
        Arrays.sort(candidates);

        backtracking(candidates, target, 0);
        return result;
    }

    private void backtracking(int[] candidates, int target, int beginIndex) {
        if (target < 0 || beginIndex >= candidates.length) {
            return;
        }
        if (target == 0) {
            result.add(new ArrayList<>(list));
            return;
        }

        for (; beginIndex < candidates.length; beginIndex++) {
            // 不能选择比当前元素更小的元素
            list.add(candidates[beginIndex]);
            backtracking(candidates, target - candidates[beginIndex], beginIndex);
            list.removeLast();
        }
    }
}

从题目中，可以看出，这是个无序数组。

如果target=7, 暴力求解，可能有[[2,2,3],[2,3,2],[3,2,2],[7]]

原因在于，每一次的递归都可以从下标0再开始查找。我们需要限定，当已经查找了下标为1的数，那么下一个递归中只能查找下标>=1的数，避免重复

40. 组合总和 II

List<List<Integer>> result = new LinkedList<>();

    LinkedList<Integer> list = new LinkedList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates); // [1,1,2,5,6,7,10]   8
        // 分析：一个组合为[1,7]  如果下一个组合仍然选1为第一个元素,那么就会重复,所以，如果当前元素和前一个元素相同，跳过当前元素
        backtracking(candidates, target, 0);
        return result;
    }

    private void backtracking(int[] candidates, int target, int beginIndex) {
        if (target == 0) {
            if (list.size() > 0) {
                result.add(new LinkedList<>(list));
                return;
            }
        }
        if (target <=0) {
            return;
        }
        for (int i = beginIndex; i < candidates.length; i++) {
            if (i != beginIndex && candidates[i] == candidates[i -1]) { // 跳过元素，注意这里是i != beginIndex
                continue;
            }
            list.add(candidates[i]);
            backtracking(candidates, target - candidates[i], i + 1);
            list.removeLast();
        }
    }

剪枝：

当识别到<=0的情况之后，这是一个逐渐增加的有序数组，后面的数字就没必要再去识别了。

 private boolean backtracking(int[] candidates, int target, int beginIndex) {
        if (target == 0) {
            if (list.size() > 0) {
                result.add(new LinkedList<>(list));
            }
        }
        if (target <= 0) {
            return false;
        }
        for (int i = beginIndex; i < candidates.length; i++) {
            if (i != beginIndex && candidates[i] == candidates[i -1]) {
                continue;
            }
            list.add(candidates[i]);
            boolean backtracking = backtracking(candidates, target - candidates[i], i + 1);
            list.removeLast();
            if (!backtracking) {
                break;
            }
        }
        // 遍历完成之后
        return true;
    }

131. 分割回文串

 List<List<String>> res = new ArrayList<>();
    LinkedList<String> cur = new LinkedList<>();


    public List<List<String>> partition(String s) {
        backtracking(s, 0, new StringBuilder());
        return res;
    }

    private void backtracking(String s, int beginSplitIndex, StringBuilder stringBuilder) {
        if (beginSplitIndex == s.length()) {
            res.add(new LinkedList<>(cur));
            return;
        }


        for (int i = beginSplitIndex; i < s.length(); i++) {
            stringBuilder.append(s.charAt(i)); // 如果i从0开始[a]，那么下一节点就是[ab]
            if (check(stringBuilder)) { // 当前这个StringBuilder是一个回文子串
                cur.add(stringBuilder.toString());
                // // 创建了一个新的StringBuilder，在下一级是从i + 1开始的。
                backtracking(s, i + 1, new StringBuilder()); //比如当前是[aab]，下一级范围在[ab]
                cur.removeLast();
            }
        }
    }


    private boolean check(StringBuilder sb) {
        for (int i = 0; i < sb.length() / 2; i++) {
            if (sb.charAt(i) != sb.charAt(sb.length() - 1 - i)) {
                return false;
            }
        }
        return true;
    }

较为有难度，后面再深刻细化，卡了挺久