算法练习第二十七天|39. 组合总和、40.组合总和II、131.分割回文串

leetcode题目链接
39. 组合总和
40.组合总和II
131.分割回文串

39. 组合总和

class Solution {
    List<Integer> path = new ArrayList();
    List<List<Integer>> result = new ArrayList();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
                result.clear();
        path.clear();
        Arrays.sort(candidates);
        backTrace(candidates,target,0,0);
        return result;
    }

    public void backTrace(int[] candidates,int target,int startIndex,int sum){
        //确定终止条件
        //if(sum > target) return;
        if(sum == target){
            result.add(new ArrayList(path));
            return;
        }
        //横向的是遍历
        //sum+candidates[i] <target
        //此处剪枝操作需要先给数组排序，如果下一层的sum（就是本层的 sum + candidates[i]）
        //已经大于target，就可以结束本轮for循环的遍历。
        for(int i = startIndex;i<candidates.length && sum+candidates[i] <=target;i++){
            sum += candidates[i];
            path.add(candidates[i]);
            //树往下递归的时候，可以使用上一个节点的元素i
            backTrace(candidates,target,i,sum);
            sum -= candidates[i];
            path.removeLast();
        }

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

40.组合总和II

class Solution {
    List<Integer> path = new ArrayList();
    List<List<Integer>> result = new ArrayList();
    boolean[] used =null;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        used = new boolean[candidates.length];
        Arrays.fill(used,false);
        Arrays.sort(candidates);
        backTrace(candidates,target,0,0,used);
        return result;
    }
    public void backTrace(int[] candidates,int target,int startIndex,int sum,boolean[] used){
        //确定终止条件
        if(sum > target) return;
        if(sum == target){
            result.add(new ArrayList(path));
            return;
        }

        for(int i = startIndex;i<candidates.length && candidates[i] + sum <= target;i++){
            //树层去重，树枝不去重
            if(i>0 && candidates[i-1] == candidates[i] && !used[i-1])
            continue;

            path.add(candidates[i]);
            sum += candidates[i];
            used[i] = true;
            backTrace(candidates,target,i+1,sum,used);
            path.removeLast();
            used[i] = false;
            sum -=candidates[i];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

131.分割回文串

class Solution {
    List<List<String>> result = new ArrayList();
    List<String> path = new ArrayList();
    public List<List<String>> partition(String s) {
        backTrace(s,0);
        return result;
    }
    public void backTrace(String s,int startIndex){
        //结束条件是截取到最后
        if(startIndex == s.length())
        {
            result.add(new ArrayList(path));
            return;
        }

        for(int i = startIndex;i<s.length();i++){
            if(isPalindrome(s,startIndex,i)){
                String str = s.substring(startIndex,i+1);
                path.add(str);
            }else continue;

            backTrace(s,i+1);
            path.removeLast();
        }
    }

//判断回文数
    public boolean isPalindrome(String s,int start,int end){
        for(int i = start, j=end;i<j;i++,j--){
            if(s.charAt(i) != s.charAt(j)){
                return false;
            }
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36