看视频都能理解,第一题可以手写,后两题不看视频完全想不到

39. 组合总和

    /**
     * <A href="https://leetcode.cn/problems/combination-sum/description/">39. 组合总和</A>
     */
    LinkedList<Integer> path = new LinkedList<>();
    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        backTracing(candidates, target, 0);
        return res;
    }

    public void backTracing(int[] candidates, int abatedTarget, int startIndex) {
        if (abatedTarget < 0) {
            return;
        }
        if (abatedTarget == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i < candidates.length; i++) {
            if (abatedTarget - candidates[i] < 0) {
                return;
            }
            path.add(candidates[i]);
            abatedTarget -= candidates[i];
            backTracing(candidates, abatedTarget, i);
            abatedTarget += candidates[i];
            path.removeLast();
        }
    }

40.组合总和II

LinkedList<Integer> path = new LinkedList<>();
    List<List<Integer>> res = new ArrayList<>();
    boolean[] used;
        /**
     * <A href="https://leetcode.cn/problems/combination-sum-ii/">40. 组合总和 II</A>
     */
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        used = new boolean[candidates.length];
        Arrays.sort(candidates);
        backTracing2(candidates, target, 0);
        return res;
    }

    public void backTracing2(int[] candidates, int abatedTarget, int startIndex) {
        if (abatedTarget == 0) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = startIndex; i < candidates.length; i++) {
            if (abatedTarget - candidates[i] < 0) {
                return;
            }
            if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) {
                continue;
            }

            path.add(candidates[i]);
            abatedTarget -= candidates[i];
            used[i] = true;
            startIndex = i + 1;
            backTracing2(candidates, abatedTarget, startIndex);
            used[i] = false;
            abatedTarget += candidates[i];
            path.removeLast();
        }
    }

131.分割回文串

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

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


    private void backTracing(String s, int startIndex) {
        if (startIndex >= s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            if (isPalindrome(s, startIndex, i)) {
                path.add(s.substring(startIndex, i + 1));
            }else {
                continue;
            }
            backTracing(s,i+1);
            path.removeLast();
        }
    }


    private boolean isPalindrome(String s, int startIndex, int end) {
        if (startIndex == end) {
            return true;
        }
        while (startIndex < end) {
            if (s.charAt(startIndex) != s.charAt(end)) {
                return false;
            }
            startIndex++;
            end--;
        }
        return true;
    }