VandanRogheliya's blog

The number of ways to break n into a sum of integers from 1 to k (Help)
By VandanRogheliya, history, 4 years ago, In English

I was practising C. k-Tree. I want to solve it by finding the difference between f(n,k) and f(n,d-1) where f will return the number of ways to break n into a sum of integers from 1 to k.

Can someone please link the resources for an iterative solution or explain it?

Thank you!

Edit: Making it less confusing:

Example:

I want to find the number of ways to make sum n=3 from using integers 1 to k=2.

1st way: 1 + 1 + 1

2nd way: 2 + 1

3rd way: 1 + 2

So total ways are 3.

Note: I can not use only 3 because it is more than k=2. If k=3 then I can also use only 3 and get 4 ways.

I can do this by recursion like this:



ll recFun(ll k, ll n, ll sum = 0) {
  if (sum == n) {
    return 1;
  } else if (sum > n) return 0;
 
 
  ll total = 0;
 
  FO(i, k) {
    total += recFun(k, n, sum+i+1);
  }
 
  return total;
}
Tags #dp
  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

[deleted]

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry, I think my blog is a bit confusing. Let me explain the doubt with an example.

    I want to find number of ways to make sum n=3 from using integers 1 to k=2.

    1st way: 1 + 1 + 1

    2nd way: 2 + 1

    3rd way: 1 + 2

    So total ways are 3.

    Note: I can not use only 3 because it is more than k=2. If k=3 then I can also use only 3 and get 4 ways.

    I can do this by recursion like this:

    ll recFun(ll k, ll n, ll sum = 0) {
  if (sum == n) {
    return 1;
  } else if (sum > n) return 0;
 
 
  ll total = 0;
 
  FO(i, k) {
    total += recFun(k, n, sum+i+1);
  }
 
  return total;
}

    I want to know how to do this in an iterative way using memoization. I will also add this OP to make it less confusing.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by VandanRogheliya (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You can do this using dp.

Suppose you want to make sum i using numbers from 1 to d.

For i=0:

dp[0]=number of ways = 1(using no numbers at all) [base case]

Then for any arbitrary i

dp[i] = sum(dp[i-j]) for all j from 1 to min(d,i) (bcoz u cant use a number greater than i to make sum i)

this works bcoz here order matters 1+2 and 2+1 are different

You can see my submission for implementation Click

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you for the explanation but I do not understand why dp[i] = sum(dp[i-j]) works?

    What is the intuition behind it?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Okay, so we are making a number i using the numbers from 1 to d right. Suppose i=a1+a2+a3+...+ap+x where all numbers ai and x belongs to [1,d]. Now focus on the last number x, it(again) can be anything belonging to [1,d], so we consider all possible options for x that will guarantee that we count all possible ways to sum to i.

      so we iterate over [1,d] (for now i am assuming i>=d else it would be min(i,d))

      suppose currently we are considering x=j, now to calculate the number of ways you can make i such that last number = j, observe that you can add the number j to all the number of ways you can make i-j. hence dp[i-j].

      Hence dp[i] = sum over all dp[i-j] where j belongs to [1,min(d,i)]

      Let's take your example n=3,d=2

      dp[0]=1 corresponds to selecting no numbers [base case]

      dp[1]=dp[1-1]=dp[0]=1 corresponds to taking only 1 (this is the only way to make 1)

      dp[2]=dp[2-1] (corresponding to 1+1) + dp[2-2] (corresponding to only 2) = dp[1]+dp[0]=1+1=2

      dp[3]=dp[3-1] (corresponding to 1+1+1 and 2+1) + dp[3-2] (corresponding to 1+2) = dp[2]+dp[1]=2+1=3

      Hence number of ways you can make 3 using 1 and 2 is 3.

      Hope my explanation was clear :)

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The point about making i from adding j and i-j did the trick! Thank you so much!

        → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Well, we can solve this with a naive Dp-approach in $$$O(n\cdot k)$$$ time and $$$O(n)$$$ Space.

Let $$$dp[n]$$$ be the amount you want. If the last taken number is $$$i$$$, then we remain with $$$n-i$$$, and this gives us the transition: $$$dp[n]=\sum_{i=1}^k dp[n-i]$$$.

We can use sliding window technique to achieve $$$O(n)$$$ time and $$$O(k)$$$ space.

Also, if $$$n$$$ is very big and $$$k$$$ is small enough (about 300) we can use matrix power to get a solution in $$$O(k^3 \cdot \log n)$$$ time and $$$O(k^2)$$$ space.

→ Reply