简介
虽然超时了, 但是我还是想把这种思想放在这里. 这肯定可以做(现在是回溯增加), 改为回溯减少一定就可以了.
code
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
void dfs(vector<int> &candidates, vector<int> &ans, vector<int> &combine, int idx) {
if(idx >= candidates.size()) {
return;
}
// 直接跳过
dfs(candidates, ans, combine, idx + 1);
// 选择当前数
combine.emplace_back(candidates[idx]);
vector<int> tmp;
tmp.assign(combine.begin(), combine.end());
sort(tmp.begin(), tmp.end(), greater<int>());
int sumAdd = 0;
for(auto it: tmp){
sumAdd += it;
}
if(sumAdd % 3 == 0) {
string s1;
for(auto it : tmp){
s1 += it + '0';
}
string s2;
for(auto it : ans){
s2 += it + '0';
}
if(s1.size() > s2.size()){
ans.clear();
ans.assign(tmp.begin(), tmp.end());
}else if(s1.size() == s2.size()){
if(s1 > s2) {
ans.clear();
ans.assign(tmp.begin(), tmp.end());
}
}
}
dfs(candidates, ans, combine, idx+1);
combine.pop_back();
//cout << idx ;
}
string largestMultipleOfThree(vector<int>& digits) {
vector<int> ans;
vector<int> combine;
dfs(digits, ans, combine, 0);
string s2;
for(auto it : ans){
s2 += it + '0';
}
if(ans.size() > 0 && ans[0] == 0){
return "0";
}
return s2;
}
};
int main() {
Solution s;
int a [] = {0,0,0,0,0,0};
vector<int> t;
t.assign(a, a+6);
cout << s.largestMultipleOfThree(t);
// string c = "123";
// string d = "43";
// if(c > d){
// cout << c;
// }
return 0;
}