Giả sử chúng ta có tập hợp các số ứng viên (tất cả phần tử duy nhất) và một số mục tiêu. Ta phải tìm tất cả các tổ hợp duy nhất trong ứng viên sao cho tổng các số ứng viên bằng mục tiêu. Cùng một số không được chọn từ ứng viên nhiều hơn một lần. Ví dụ, phần tử [2,3,6,7,8], target = 8, kết quả [[2,6],[8]].
Các bước:
- Giải quyết bằng đệ quy. Hàm solve() nhận index, mảng a, số nguyên b, mảng temp.
- Định nghĩa mảng res rỗng
- nếu b = 0, thêm temp vào res, return
- nếu index = kích thước a, return
- nếu b < 0, return
- sắp xếp mảng a
- for i in range index đến kích thước a – 1
- nếu i > index và a[i] = a[i – 1], continue
- thêm a[i] vào temp
- solve(i + 1, a, b – a[i], temp)
- xóa phần tử cuối temp
- gọi solve(0, a, b, temp)
- return res
Hãy xem triển khai sau:
Ví dụ
#include <bits/stdc++.h> using namespace std; void print_vector(vector<vector<int> > v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << "["; for(int j = 0; j <v[i].size(); j++){ cout << v[i][j] << ", "; } cout << "],"; } cout << "]"<<endl; } class Solution { public: vector < vector <int> > res; void solve(int idx, vector <int> &a, int b, vector <int> temp){ if(b == 0){ res.push_back(temp); return; } if(idx == a.size())return; if(b < 0)return; sort(a.begin(), a.end()); for(int i = idx; i < a.size(); i++){ if(i > idx && a[i] == a[i-1])continue; temp.push_back(a[i]); solve(i + 1, a, b - a[i], temp); temp.pop_back(); } } vector<vector<int> > combinationSum2(vector<int> &a, int b) { res.clear(); vector <int> temp; solve(0, a, b, temp); return res; } }; main(){ Solution ob; vector<int> v = {2,3,6,7,8}; print_vector(ob.combinationSum2(v, 10)) ; }Input
[2,3,6,7,8] 8
Output
[[2, 8, ],[3, 7, ],]