資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
服裝研究
法律研究C++組合數 II
假設我們有一組候選數字（所有元素都是唯一的）和一個目標數字。我們必須找到候選數字中所有唯一的組合，其中候選數字之和等於給定的目標值。同一個數字不會從候選數字中選擇超過一次。所以如果元素是[2,3,6,7,8]，目標值是8，那麼可能的輸出將是[[2,6],[8]]
讓我們看看步驟：
- 我們將以遞迴的方式解決這個問題。遞迴函式名為solve()。它接受索引、陣列a、整數b和另一個數組temp。solve方法的工作方式如下：
- 定義空陣列res
- 如果b = 0，則將temp插入res並返回
- 如果index = a的大小，則返回
- 如果b < 0，則返回
- 對陣列a進行排序
- 對於i的範圍從index到a的大小-1
- 如果i > index並且a[i] = a[i – 1]，則繼續
- 將a[i]插入temp
- solve(i + 1, a, b – a[i], temp)
- 刪除temp中的最後一個元素
- 透過傳遞index = 0、陣列a和目標b以及另一個數組temp來呼叫solve()方法
- 返回res
讓我們看看下面的實現來更好地理解：
示例
#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)) ;
}輸入
[2,3,6,7,8] 8
輸出
[[2, 8, ],[3, 7, ],]
更新於：2020年5月4日
439 次瀏覽
廣告