LeetCode DayBackTracking パート 2

39. 組み合わせ合計

個別の整数候補の配列とターゲット整数 target を指定すると、選択された数値の合計が target になる、候補の一意のすべての組み合わせのリストを返します。組み合わせは任意の順序で返すことができます。

同じ番号を候補から無制限に選択できます。
の場合、2 つの組み合わせは一意です。 頻度
選択した数字の少なくとも 1 つが異なります。

テスト ケースは、指定された入力に対して、ターゲットに達する一意の組み合わせの合計が 150 個未満になるように生成されます。

例 1:

入力: 候補 = [2,3,6,7]、ターゲット = 7
出力: [[2,2,3],[7]]
説明:
2 と 3 が候補で、2 + 2 + 3 = 7 となります。2 は複数回使用できることに注意してください。
7 が候補で、7 = 7.
組み合わせはこの 2 つだけです。
例 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. 組み合わせ和Ⅱ

制限時間を超えました

    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 つあるため、2 番目の「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 を分割します。 部分文字列
パーティションのは
回文
。 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 DayBackTracking パート 2の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。