Jumlah Gabungan II

40. Gabungan Jumlah II

Kesukaran: Sederhana

Topik: Tatasusunan, 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 digunakan sekali dalam 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 <= candidates.length <= 100
• 1 <= calon[i] <= 50
• 1 <= sasaran <= 30

Penyelesaian:

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

Mari 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 hasil.
   • Kami mengulangi calon bermula dari indeks semasa. Jika calon adalah sama seperti yang sebelumnya, kami melangkaunya untuk mengelakkan gabungan 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 menghabiskan semua kemungkinan.
3. Pemangkasan: 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.

Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi 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!