Dynamic programming with Combination sum inner loop and outer loop interchangeable?

Question

I am a little confuse about the dynamic programming solution for combination sum, that you are given a list of numbers and a target total, and you want to count how many ways you can sum up to this target sum. Numbers can be reused multiple times. I am confused about the inner loop and outer loop that whether they are interchangeable or not. Can some explain the difference between the following two, and in what case we would use one but not the other, or they are the same.

int [] counts = new int[total];
counts[0] = 1;

// (1) 
for(int i = 0; i <= total; i++) {
   for(int j = 0; j < nums.length; j++) {
       if(i >= nums[j])
          counts[i] += counts[i - nums[j]];
   }
}

// (2)
for(int j = 0; j < nums.length; j++)
   for(int i = nums[j]; i <= total; i++) {
       counts[i] += counts[i - nums[j]];
   }
}

Answer 1

The two versions are indeed different, yielding different results.

I'll use nums = {2, 3} for all examples below.

Version 1 finds the number of combinations with ordering of elements from nums whose sum is total. It does so by iterating through all "subtotals" and counting how many combinations have the right sum, but it doesn't keep track of the elements. For example, the count for 5 will be 2. This is the result of using the first element (with value 2) and finding 1 combination in nums[3] and another combination for the second element (value 3) with the 1 combination in nums[2]. You should pay attention that both combinations use a single 2 and a single 3, but they represent the 2 different ordered lists [2, 3] & [3, 2].

Version 2 on the other hand find the number of combinations without ordering of elements from nums whose sum is total. It does so by counting how many combinations have the right sum (fur each subtotal), but contrary to version 1, it "uses" each element completely before moving on to the next element thus avoiding different orderings of the same group. When counting subtotals with the first element (2), all counts will initially be 0 (except the 0 sum sentinel), and any even subtotal will get the new count of 1. When the next element used, it is as if it's coming after all 2's are already in the group, so, contrary to version 1, only [2, 3] is counted, and not [3, 2].

By the way, the order of elements in nums doesn't affect the results, as can be understood by the logic explained.