clueless coding // TODO: be smarter

LeetCode 377. Combination Sum IV: C++ Solution



Problem Statement


Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Function Signature (C++):
  int combinationSum4(vector<int>& nums, int target)

Inputs:
  nums = [1, 2, 3]
  target = 4

Outputs:
[
  [1, 1, 1, 1],
  [1, 1, 2],
  [1, 2, 1],
  [1, 3],
  [2, 1, 1],
  [2, 2],
  [3, 1],
]



TL;DR Code Solution


int combinationSum4(vector<int>& nums, int target) {

    vector<int> dp(target + 1, 0);
    dp[0] = 1;

    for (int i = 1; i <= target; i++) {
        for (int num : nums) {
            if (i - num >= 0) {
                dp[i] += dp[i - num];
            }
        }
    }

    return dp[target];

}