個別の整数候補の配列とターゲット整数 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]; }
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; } }
文字列 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 サイトの他の関連記事を参照してください。