LeetCode DayBack추적 파트 2

39. 조합 합계

고유한 정수 후보 배열과 목표 정수 목표가 주어지면 선택한 숫자의 합이 목표와 일치하는 모든 고유한 후보 조합 목록을 반환합니다. 어떤 순서로든 조합을 반환할 수 있습니다.

동일한 번호는 후보자 중에서 무제한으로 선택할 수 있습니다.
인 경우 두 가지 조합이 고유합니다. 빈도
선택한 번호 중 하나 이상이 다릅니다.

테스트 케이스는 주어진 입력에 대해 목표에 합산되는 고유 조합 수가 150개 미만의 조합이 되도록 생성됩니다.

예 1:

입력: 후보 = [2,3,6,7], 대상 = 7
출력: [[2,2,3],[7]]
설명:
2와 3이 후보이고 2 + 2 + 3 = 7입니다. 2는 여러 번 사용할 수 있으니 참고하세요.
7이 후보이고, 7=7입니다.
이 두 가지 조합뿐입니다.
예시 2:

입력: 후보 = [2,3,5], 대상 = 8
출력: [[2,2,2,2],[2,3,3],[3,5]]
예시 3:

입력: 후보 = [2], 대상 = 1
출력: []

제약사항:

1 2 후보자의 모든 요소는 서로 다릅니다.
1

원본 페이지

이 문제와 어제 풀었던 문제의 차이는 그리 크지 않습니다.


BackTracking은 깊이 가능성을 검색하고 너비 제어를 위해 루프를 사용하는 데 여전히 잘 작동합니다.


주의가 필요한 부분은 여기에 동일한 요소를 추가한 다음 전체 조합을 고유하게 유지할 수 있다는 것입니다.

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> combs = new LinkedList<>();
        backTracking(list, combs, candidates, target, 0, 0);
        return list;
    }

    public void backTracking(List<List<Integer>>list, List<Integer> combs, int[] candidates, int target, int sum, int start){
        if(sum > target){
            return;
        }
        if(sum == target){
            list.add(new ArrayList<>(combs));
            return;
        }

        for(int i=start; i<candidates.length; i++){
            combs.add(candidates[i]);
            sum += candidates[i];
            backTracking(list, combs, candidates, target, sum, i);
            combs.remove(combs.size()-1);
            sum -= candidates[i];
        }

40. 조합합 II

시간 제한이 초과되었습니다

    Set<List<Integer>> set = new HashSet<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<Integer> combs = new LinkedList<>();
        Arrays.sort(candidates);
        backTracking(combs, target, candidates, 0, 0);

        return new ArrayList<>(set);
    }

    public void backTracking(List<Integer> combs, int target, int[]candidates, int start, int sum){
        if(sum > target){
            return;
        }
        if(sum == target){
            set.add(new ArrayList<>(combs));
        }

        for(int i=start; i<candidates.length; i++){
            if(candidates[i] + sum > target){
                continue;
            }

            sum += candidates[i];
            combs.add(candidates[i]);
            backTracking(combs, target, candidates, i+1, sum);
            sum -= candidates[i];
            combs.remove(combs.size()-1);

        }
    }

예를 들어 이전에 사용되었던 일부 요소가 있기 때문입니다. [1,1,1,2,3] 112는 첫 번째 재귀에서 사용되었지만 루프는 1부터 3까지 시작하는 모든 요소를 ​​순회하며 '1'이 3개 있으므로 두 번째 '1'이 되면 이전 재귀 단계에서 발견된 조합 112도 발견되므로 이러한 중복 단계를 줄여야 합니다(마찬가지로 재귀의 순회 및 재귀의 순회에서도 발생할 수 있습니다.

문제를 해결하세요

    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<Integer> combs = new LinkedList<>();
        Arrays.sort(candidates);
        backTracking(combs, target, candidates, 0, 0, false);

        return list;
    }

    public void backTracking(List<Integer> combs, int target, int[]candidates, int start, int sum, boolean horizon){
        if(sum > target){
            return;
        }
        if(sum == target){
            list.add(new ArrayList<>(combs));
        }

        for(int i=start; i<candidates.length; i++){
            if(candidates[i] + sum > target){
                continue;
            }

            if(i!=0 && candidates[i] == candidates[i-1] && horizon){
                continue;
            }

            sum += candidates[i];
            combs.add(candidates[i]);
            backTracking(combs, target, candidates, i+1, sum, false);
            sum -= candidates[i];
            combs.remove(combs.size()-1);
            horizon = true;
        }
    }

131. 회문 분할

문자열 s가 주어지면 모든
하위 문자열
파티션의
회문
. s의 가능한 모든 회문 분할을 반환합니다.

예 1:

입력: s = "aab"
출력: [["a","a","b"],["aa","b"]]
예시 2:

입력: s = "a"
출력: [["a"]]

제약사항:

1 s에는 영문 소문자만 포함됩니다.
원본페이지

    List<List<String>> list = new ArrayList<>();
    public List<List<String>> partition(String s) {
        List<String> combs = new ArrayList<>();

        backTracking(combs, new StringBuilder(s), 0);
        return list;
    }

    public void backTracking(List<String> combs, StringBuilder str, int start){
        if(start == str.length()){
            list.add(new ArrayList<>(combs));
            return;
        }

        for(int i=1; i+start <= str.length(); i++){

            String cur = str.substring(start, start+i);

            if(!isParlindrome(cur)){
                continue; 
            } 

            combs.add(cur);
            backTracking(combs, str, start+i);
            combs.remove(combs.size()-1);
        }

    }

    public boolean isParlindrome(String s){
        int left = 0;
        int right = s.length()-1;

        while(left<right){
            if(s.charAt(left++)!=s.charAt(right--)){
                return false;
            }
        }
        return true;
    }

위 내용은 LeetCode DayBack추적 파트 2의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!