Efficient way to find number of sums possible

Question

Given three integers n, k and d, how many ways can n be represented as sum of positive integers i<=k, such that d occurs at least once in the sum. It is guarenteed that 0<d<=k. My approach was a recursive one;

#include <stdio.h>
#include <stdlib.h>
int n,k,d,ans=0;
void solve(int totw,int flag)//totw is the total sum till now, and flag is to keep track of the number of d's in the sum.
{
    if(totw>n)
        return;
    if(totw==n && flag>0)//flag>0--->at least 1 d
    {
        ans = (ans+1)%1000000007;//answer is expected modulo 10^9+7
        return;
    }
    int i=1,h=k;
    if(h>n-totw)
        h=n-totw;
    while(i<=h)
    {
        if(i==d)
            flag++;
        solve(totw+i,flag);
        i++;
    }
}
int main()
{
    scanf("%d %d %d",&n,&k,&d);
    solve(0,0);
    printf("%d",ans);
}

Input:
3 3 2
Output:
2
But the judge shows Time Limit Exceeded. Is there any more efficient algorithm to proceed with in this case? 0<n,k<=100
PS:I was just wondering whether there is any combinatoric argument that can solve this question without recursion or iteration. And yes....order of sums matter.

Answer 1

You can represent your recursive calls as a graph. Each node is given by the parameters of your function (totw, flag), and you add an edge whenever you make a recursive call. There are about n*2 nodes and n*2*k edges in this graph.

This graph has a very interesting property: it is a DAG (e.g. because totw is strictly increasing at each call). Therefore, when you call solve(totw, flag), you can keep the result in an array, so that you don't compute it twice.

This is actually a way to explain dynamic programming: an algorithm to find the shortest path in a DAG (with slight modifications it can also compute the longest path/the number of paths, but you get the idea). The time complexity on a graph G = (V, E) will be a O(|V|+|E|) (that's actually a kind of amortized analysis).

Thus, keeping the results in an array will result in a O(nk) time complexity.

Actually you can make the implementation even shorter by changing slightly the graph:

enum { UNKNOWN = -1 };

/* not tested */
/* solve(num, d_seen): returns the answer to the problem with a sum
   target, knowing whether `d` was already used */
int solve(int sum, int d_seen)
{
  if (sum == 0) return d_seen;
  int ans = dp[sum][d_seen];
  if (ans == UNKNOWN) {
    ans = 0;
    /* min(a, b) being what it is supposed to be */
    for (int i = 1; i <= min(sum, k); ++i)
      ans = (ans + solve(sum - i, d_seen || (i == d))) % MOD;
  }

  return (dp[sum][d_seen] = ans);
}

By the way you don't put flag back to 0 after incrementing it.