Jumlah Gabungan II

40. Jumlah Gabungan II

Kesukaran:Sederhana

Topik:Susunan, Menjejak Belakang

Memandangkan koleksi nombor calon (calon) dan nombor sasaran (sasaran), cari semua kombinasi unik dalam calon di mana nombor calon dijumlahkan untuk disasarkan.

Setiap nombor dalam calon hanya boleh digunakansekalidalam gabungan.

Nota:Set penyelesaian mestilah tidak mengandungi gabungan pendua.

Contoh 1:

• Input:calon = [10,1,2,7,6,1,5], sasaran = 8
• Output:[[1,1,6], [1,2,5], [1,7], [2,6]]

Contoh 2:

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

Kekangan:

• 1 <= calon.panjang <= 100
• 1 <= calon[i] <= 50
• 1 <= sasaran <= 30

Penyelesaian:

Kita boleh menggunakan pendekatan menjejak ke belakang. Idea utama ialah mengisih tatasusunan terlebih dahulu untuk mengendalikan pendua dengan mudah dan kemudian meneroka semua kombinasi yang mungkin menggunakan penjejakan ke belakang.

Mari kita laksanakan penyelesaian ini dalam PHP:40. Jumlah Gabungan II

Penjelasan:

1. Isih: Tatasusunan calon diisih untuk mengendalikan pendua dengan mudah dan untuk memastikan gabungan dibentuk dalam susunan yang disusun.
2. Backtracking: Fungsi backtrack digunakan untuk meneroka semua kemungkinan kombinasi.
   • Jika sasaran menjadi sifar, kami menambah gabungan semasa pada hasilnya.
   • Kami mengulangi calon bermula dari indeks semasa. Jika calon sama dengan yang sebelumnya, kami langkau untuk mengelakkan kombinasi pendua.
   • Kami menolak calon semasa daripada sasaran dan secara rekursif memanggil fungsi backtrack dengan sasaran baharu dan indeks seterusnya.
   • Panggilan rekursif diteruskan sehingga kami sama ada menemui gabungan yang sah atau habiskan semua kemungkinan.
3. Pruning: Jika calon melebihi sasaran, kami keluar dari gelung lebih awal kerana calon selanjutnya juga akan melebihi sasaran.

Kod ini akan mengeluarkan semua kombinasi unik yang dijumlahkan kepada sasaran sambil memastikan setiap calon digunakan sekali sahaja dalam setiap kombinasi.

Hubungi Pautan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberirepositoribintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna buat saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:

• LinkedIn
• GitHub

Atas ialah kandungan terperinci Jumlah Gabungan II. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!