1449. Form Largest Integer With Digits That Add up to Target Hard

1/**
2 * [1449] Form Largest Integer With Digits That Add up to Target
3 *
4 * Given an array of integers cost and an integer target, return the maximum integer you can paint under the following rules:
5 * 
6 * 	The cost of painting a digit (i + 1) is given by cost[i] (0-indexed).
7 * 	The total cost used must be equal to target.
8 * 	The integer does not have 0 digits.
9 * 
10 * Since the answer may be very large, return it as a string. If there is no way to paint any integer given the condition, return "0".
11 *  
12 * Example 1:
13 * 
14 * Input: cost = [4,3,2,5,6,7,2,5,5], target = 9
15 * Output: "7772"
16 * Explanation: The cost to paint the digit '7' is 2, and the digit '2' is 3. Then cost("7772") = 2*3+ 3*1 = 9. You could also paint "977", but "7772" is the largest number.
17 * Digit    cost
18 *   1  ->   4
19 *   2  ->   3
20 *   3  ->   2
21 *   4  ->   5
22 *   5  ->   6
23 *   6  ->   7
24 *   7  ->   2
25 *   8  ->   5
26 *   9  ->   5
27 * 
28 * Example 2:
29 * 
30 * Input: cost = [7,6,5,5,5,6,8,7,8], target = 12
31 * Output: "85"
32 * Explanation: The cost to paint the digit '8' is 7, and the digit '5' is 5. Then cost("85") = 7 + 5 = 12.
33 * 
34 * Example 3:
35 * 
36 * Input: cost = [2,4,6,2,4,6,4,4,4], target = 5
37 * Output: "0"
38 * Explanation: It is impossible to paint any integer with total cost equal to target.
39 * 
40 *  
41 * Constraints:
42 * 
43 * 	cost.length == 9
44 * 	1 <= cost[i], target <= 5000
45 * 
46 */
47pub struct Solution {}
48
49// problem: https://leetcode.com/problems/form-largest-integer-with-digits-that-add-up-to-target/
50// discuss: https://leetcode.com/problems/form-largest-integer-with-digits-that-add-up-to-target/discuss/?currentPage=1&orderBy=most_votes&query=
51
52// submission codes start here
53
54impl Solution {
55    pub fn largest_number(cost: Vec<i32>, target: i32) -> String {
56        String::new()
57    }
58}
59
60// submission codes end
61
62#[cfg(test)]
63mod tests {
64    use super::*;
65
66    #[test]
67    fn test_1449() {
68    }
69}
70