Combination Sum IV: the idea to remember.

The core insight

For each total, append each possible final value to every sequence reaching total minus that value.

Why it works

Every sequence has one final value, so these cases partition the answer without duplication. The empty sequence makes dp[0]=1.

The mistake to avoid

Put total in the outer loop. Reversing the loop order counts unordered combinations. This is problem 377 in the original Blind 75 links, not problem 39.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

int combinationSum4(int[] nums, int target) {
    long[] dp = new long[target + 1];
    dp[0] = 1;
    for (int total = 1; total <= target; total++) {
        for (int n : nums) if (n <= total) {
            // Values beyond int range cannot affect an int-sized final answer:
            // all counts are nonnegative, so saturation is safe.
            dp[total] = Math.min(Integer.MAX_VALUE, dp[total] + dp[total - n]);
        }
    }
    return (int) dp[target];
}

Make the next connection