LeetCode DayBackTracking Bahagian 2

39. Jumlah Gabungan

Memandangkan tatasusunan calon integer yang berbeza dan sasaran integer sasaran, kembalikan senarai semua gabungan unik calon yang jumlah nombor yang dipilih untuk disasarkan. Anda boleh mengembalikan gabungan dalam sebarang susunan.

Nombor yang sama boleh dipilih daripada calon tanpa had bilangan kali. Dua kombinasi adalah unik jika
kekerapan
daripada sekurang-kurangnya satu daripada nombor yang dipilih adalah berbeza.

Kes ujian dijana supaya bilangan gabungan unik yang dijumlahkan kepada sasaran adalah kurang daripada 150 kombinasi untuk input yang diberikan.

Contoh 1:

Input: calon = [2,3,6,7], sasaran = 7
Output: [[2,2,3],[7]]
Penjelasan:
2 dan 3 ialah calon, dan 2 + 2 + 3 = 7. Ambil perhatian bahawa 2 boleh digunakan beberapa kali.
7 ialah calon, dan 7 = 7.
Ini adalah dua kombinasi sahaja.
Contoh 2:

Input: calon = [2,3,5], sasaran = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
Contoh 3:

Input: calon = [2], sasaran = 1
Output: []

Kekangan:

1 <= candidates.length <= 30
2 <= calon[i] <= 40
Semua elemen calon adalah berbeza.
1 <= sasaran <= 40

Halaman Asal

Perbezaan antara soalan ini dan soalan yang diselesaikan semalam tidak begitu besar.


BackTracking masih berfungsi dengan baik untuk mencari kemungkinan kedalaman dan menggunakan gelung untuk kawalan lebar.


Bahagian yang memerlukan perhatian ialah di sini kita boleh menambah elemen yang sama dan kemudian mengekalkan keseluruhan gabungan itu unik.

    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];
        }




</p>
<h2>
  
  
  40. Jumlah Gabungan II
</h2>

<h3>
  
  
  Had Masa Melebihi
</h3>



<pre class="brush:php;toolbar:false">    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);

        }
    }

Kerana terdapat beberapa elemen yang telah digunakan sebelum ini cth. [1,1,1,2,3] 112 telah digunakan dalam rekursi pertama tetapi gelung akan merentasi semua elemen yang bermula dari 1 hingga 3 dan terdapat tiga '1', jadi apabila ia datang ke '1' kedua, gabungan 112 juga akan ditemui, yang telah ditemui dalam langkah rekursi sebelumnya, jadi kita harus mengurangkan langkah berlebihan ini (begitu juga ia mungkin berlaku dalam rekursi rekursi dan rekursi melintang rekursi juga.

Selesaikan masalah

    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. Pembahagian Palindrom

Diberi rentetan s, partition s supaya setiap
subrentetan
daripada partition ialah
palindrom
. Kembalikan semua pembahagian palindrom yang mungkin bagi s.

Contoh 1:

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]
Contoh 2:

Input: s = "a"
Output: [["a"]]

Kekangan:

1 <= s.panjang <= 16
s mengandungi hanya huruf kecil Inggeris.
Halaman Asal

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

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

    public void backTracking(List 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
Atas ialah kandungan terperinci LeetCode DayBackTracking Bahagian 2. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!