title: What is the time complexity of this coin changing combination algorithm?
body: <p>Hello I have just solved this leetcode question: <a href="https://leetcode.com/problems/coin-change-2/" rel="nofollow noreferrer">https://leetcode.com/problems/coin-change-2/</a></p>
  
  <p>The objective is to find the number of different possible combinations of <code>coins</code> we can use to generate an <code>amount</code> assuming we have an infinite number of coins from each denomination.</p>
  
  <p>I know this problem has a DP solution that runs in <code>O(amount*len(coins))</code> and I can add memoization to the solution below to achieve that.</p>
  
  <p>However I am struggling to find the time complexity of the naïve approach below:</p>
  
  <pre><code>def change(amount, coins):
      def helper(amount, coins, id):
          if amount == 0:
              return 1
          res = 0
          for i in range(id, len(coins)):
              if coins[i] &lt;= amount:
                  res += helper(amount - coins[i], coins, i)
          return res
  
      res = helper(amount, coins, 0)
      return res
  </code></pre>
  
  <p>So what I am actually doing is a DFS where I try to use the first coin as much as possible before backtracking and moving to the next coin. So once I start to use the next coin I can't use the first one again --> this allows me to not count permutations in my result.</p>
  
  <p>I know the time complexity of this solution is <code>O(exponential)</code> and I also know it is <code>O(V + E)</code> because it is DFS. </p>
  
  <p>Can someone give the exact form of the time complexity ? What is the exponential term exactly ? Or how can I count the edges and vertices in my graph ?</p>