I like to read this solution as a small machine: keep the useful information, throw away the noise. For 1449. Form Largest Integer With Digits That Add up to Target, the solution in this repository is mainly a dynamic programming solution.
Guide
What?
The first job is to translate the English prompt into state, transition, and stopping conditions. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: dynamic programming, backtracking.
The notes already sitting in the source point us in the right direction:
- backtracking, combination of digits
- TLE
- 4 / 96 test cases passed.
Guide
When?
This is the kind of solution you want when the problem has structure hiding inside a messy-looking input. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are backtrack, largestNumber, stringDigitMax.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- A set is doing the membership or uniqueness work, which keeps the main loop readable.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
01//backtracking, combination of digits
02//TLE
03//4 / 96 test cases passed.
04class Solution {
05public:
06 void backtrack(int target, vector<int>& cost, string& ans, string& cur){
07 if(target == 0){
08 if(cur.size() > ans.size()){
09 ans = cur;
10 }else if(cur.size() == ans.size() && cur > ans){
11 ans = cur;
12 }
13 return;
14 }
15
16 if(target < 0){
17 return;
18 }
19
20 //target > 0
21 for(int i = 0; i < cost.size(); i++){
22 if(cost[i] <= target){
23 cur += (char)(i+1+'0');
24 backtrack(target- cost[i], cost, ans, cur);
25 cur.pop_back();
26 }
27 }
28 }
29
30 string largestNumber(vector<int>& cost, int target) {
31 string ans;
32 string cur;
33 backtrack(target, cost, ans, cur);
34
35 if(ans == "") ans = "0";
36
37 return ans;
38 }
39};
40
41//backtracking, combination of unique costs
42//TLE
43//31 / 96 test cases passed.
44class Solution {
45public:
46 void backtrack(int target, set<int>& ucost, set<vector<int>>& results, vector<int>& result){
47 if(target == 0){
48 results.insert(result);
49 return;
50 }
51
52 if(target < 0){
53 return;
54 }
55
56 //target > 0
57 for(int c : ucost){
58 if(c <= target){
59 result.push_back(c);
60 backtrack(target-c, ucost, results, result);
61 result.pop_back();
62 }
63 }
64 }
65
66 string largestNumber(vector<int>& cost, int target) {
67 string ans;
68 string cur;
69 set<vector<int>> results;
70 vector<int> result;
71
72 map<int, int> cost2maxNum;
73 for(int i = 0; i < cost.size(); i++){
74 cost2maxNum[cost[i]] = max(cost2maxNum[cost[i]], i+1);
75 }
76
77 set<int> ucost(cost.begin(), cost.end());
78
79 backtrack(target, ucost, results, result);
80
81 if(results.size() == 0) ans = "0";
82
83 for(vector<int> res : results){
84 if(res.size() < ans.size()) continue;
85 cur = "";
86 for(int r : res){
87 cur += (char)('0'+cost2maxNum[r]);
88 }
89 if(cur.size() > ans.size()){
90 ans = cur;
91 }else if(cur.size() == ans.size()){
92 ans = max(ans, cur);
93 }
94 }
95
96 // cout << "================" << endl;
97 return ans;
98 }
99};
100
101//DP
102//Runtime: 308 ms, faster than 66.67% of C++ online submissions for Form Largest Integer With Digits That Add up to Target.
103//Memory Usage: 117.5 MB, less than 100.00% of C++ online submissions for Form Largest Integer With Digits That Add up to Target.
104class Solution {
105public:
106 string stringDigitMax(string s1, string s2){
107 if(s1.size() == s2.size()){
108 return (s1 > s2) ? s1 : s2;
109 }
110
111 return (s1.size() > s2.size()) ? s1 : s2;
112 };
113
114 string largestNumber(vector<int>& cost, int target) {
115 //padding ahead
116 vector<string> dp(target+1);
117
118 map<int, int> cost2maxNum;
119 for(int i = 0; i < cost.size(); i++){
120 //skip the digits whose cost is larger than target
121 if(cost[i] > target) continue;
122 //don't need max here because smaller (i+1) will be overwritten later
123 cost2maxNum[cost[i]] = i+1;
124 //base case
125 dp[cost[i]] = to_string(i+1);
126 }
127
128 for(auto it = cost2maxNum.begin(); it != cost2maxNum.end(); it++){
129 // cout << "cost: " << it->first << ", digit: " << it->second << endl;
130 }
131
132 for(int i = 1; i <= target; i++){
133 for(auto it = cost2maxNum.begin(); it != cost2maxNum.end(); it++){
134 if(it->first > i) break;
135 //to ensure it's a valid split
136 if(dp[i-it->first] == "") continue;
137 dp[i] = stringDigitMax(dp[i], dp[it->first]+dp[i-it->first]);
138 // cout << i << ": " << dp[i] << endl;
139 }
140 }
141
142 return (dp[target] == "") ? "0" : dp[target];
143 }
144};Cost