title: number of subsequences whose sum is divisible by k
body: <p>I just did a coding challenge for a company and was unable to solve this problem. Problem statement goes like:</p>
  
  <p><strong>Given an array of integers, find the number of subsequences in the array whose sum is divisible by k, where k is some positive integer.</strong></p>
  
  <p>For example, for <code>[4, 1, 3, 2]</code> and <code>k = 3</code>, the solution is 5. <code>[[3], [1, 2], [4,3,2], [4,2], [1,3,2]]</code> are the subsequences whose sum is divisible by <code>k</code>, i.e. <code>current_sum + nums[i] % k == 0</code>, where <code>nums[i]</code> is the current element in the array.</p>
  
  <p>I tried to solve this recursively, however, I was unable to pass any test cases. My recursive code followed something like this:</p>
  
  <pre><code>def kSum(nums, k):
      def kSum(cur_sum, i):
          if i == len(nums): return 0
          sol = 1 if (cur_sum + nums[i]) % k == 0 else 0
          return sol + kSum(cur_sum, i+1) + kSum(cur_sum + nums[i], i+1)
      return kSum(0, 0)
  </code></pre>
  
  <p>What is wrong with this recursive approach, and how can I correct it? I'm not interested in an iterative solution, I just want to know why this recursive solution is wrong and how I can correct it.</p>