Form Largest Integer With Digits That Add Up To Target - Leetcode Solution

The "Form Largest Integer With Digits That Add Up To Target" problem on LeetCode asks us to find the largest possible integer that can be formed by using digits from 1 to 9 whose sum equals a given target.

To solve this problem, we can use dynamic programming. We will create a 1D array with the size of the target value plus one, which will hold the maximum possible number that can be formed using that target value. We will initialize the array with -1 values.

Next, we will iterate over all the digits from 1 to 9 and for each digit, we will calculate the remaining target value after choosing that digit. If the remaining target value is greater than or equal to 0, we will recursively call the function to calculate the maximum possible number that can be formed.

We will continue this process until the remaining target value becomes 0. At this point, we will update the array at the index corresponding to the target value with the maximum possible number that can be formed.

Finally, we will return the maximum number that can be formed using the target value.

Here's the Python implementation:

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        # initialize the dp array with -1 values
        dp = [-1] * (target + 1)
        dp[0] = 0

        # iterate over all the digits from 1 to 9
        for i in range(1, 10):
            # calculate the remaining target value after choosing this digit
            rem_target = target - cost[i - 1]

            # if the remaining target value is greater than or equal to 0,
            # recursively call the function to calculate the maximum possible
            # number that can be formed using the remaining target value
            if rem_target >= 0:
                # add the chosen digit to the maximum number that can be formed
                max_num = self.largestNumber(cost, rem_target)
                if max_num == -1:
                    continue
                max_num = str(i) + max_num

                # update the dp array at the index corresponding to the target value
                if dp[target] == -1 or len(max_num) > len(dp[target]) or (len(max_num) == len(dp[target]) and max_num > dp[target]):
                    dp[target] = max_num

        # return the maximum number that can be formed using the target value
        return dp[target] if dp[target] != -1 else "0"

The time complexity of this solution is O(target * 9), and the space complexity is O(target).

1