title: dynamic programming--find target sum ways in an array
body: <p>I encountered a problem in leetcode, I looked other's solution which used DP, but there is something that I can't understand, hope you can give me some hints.</p>
  
  <p>The problem is: Given a non-empty array containing only positive integers, find how many ways to choose some of these integers whose sum equal to target S.</p>
  
  <p>The solution is:</p>
  
  <pre><code>int findTargetSumWays(vector&lt;int&gt;&amp; nums, int S) 
  {
      int n = nums.size();
      vector&lt;int&gt; dp(S+1, 0);
  
      dp[0] = 1;
      for(int i=0; i&lt;n; i++)
          for(int j=S; j&gt;=nums[i]; j--)
          //for(int j=nums[i]; j&lt;=S; j++) //why it is wrong?
          {
  
              dp[j] += dp[j-nums[i]];
          }
      return dp[S];  
  }
  </code></pre>
  
  <p>In the code, the second loop counts from S downward to nums[i], but why it cannot be counted from nums[i] upward to S? I know if count upward, the result will be much bigger than the answer, but I can't figure out the nature problem of counting upward. </p>
  
  <p>any help is appreciated!</p>