Form largest integer with digits that add up to target

Array Dynamic Programming

49.5% acceptance

Feb 25, 2026

720

Given an array of integers cost and an integer target, return the maximum integer you can paint under the following rules: The cost of painting a digit (i + 1) is given by cost[i] (0-indexed). The total cost used must be equal to target. The integer does not have 0 digits. 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".

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn largest_number(cost: Vec<i32>, target: i32) -> String {
    let target = target as usize;
    let mut dp = vec![i32::MIN; target + 1];
    dp[0] = 0;
    for i in 1..=target {
      for &c in &cost {
        let c = c as usize;
        if i >= c && dp[i-c] != i32::MIN {
          dp[i] = dp[i].max(dp[i-c] + 1);
        }
      }
    }
    if dp[target] == i32::MIN { return "0".to_string(); }
    let mut result = String::new();
    let mut remaining = target;
    while remaining > 0 {
      for d in (0..9usize).rev() {
        let c = cost[d] as usize;
        if remaining >= c && dp[remaining - c] != i32::MIN && dp[remaining - c] == dp[remaining] - 1 {
          result.push(char::from_digit(d as u32 + 1, 10).unwrap());
          remaining -= c;
          break;
        }
      }
    }
    result
  }
}