title: count number of partitions of a set with n elements into k subsets
body: <p>This program is for count number of partitions of a set with n elements into k subsets I am confusing here <code>return k*countP(n-1, k) + countP(n-1, k-1);</code> 
  can some one explain what is happening here?
  why we are multiplying with k?</p>
  
  <p>NOTE->I know this is not the best way to calculate number of partitions that would be DP</p>
  
  <pre><code>// A C++ program to count number of partitions 
  // of a set with n elements into k subsets 
  #include&lt;iostream&gt; 
  using namespace std; 
  
  // Returns count of different partitions of n 
  // elements in k subsets 
  int countP(int n, int k) 
  { 
      // Base cases 
      if (n == 0 || k == 0 || k &gt; n) 
          return 0; 
      if (k == 1 || k == n) 
          return 1; 
  
      // S(n+1, k) = k*S(n, k) + S(n, k-1) 
      return k*countP(n-1, k) + countP(n-1, k-1); 
  } 
  
  // Driver program 
  int main() 
  { 
      cout &lt;&lt; countP(3, 2); 
      return 0; 
  } 
  </code></pre>