C++ division 재귀함수

알고리즘

C++ division 재귀함수

Chars4785 2019. 2. 27. 11:04

예제 입력

예제 출력

4+1
3+2
3+1+1
2+2+1
2+1+1+1
1+1+1+1+1
6

20 이하 숫자만 줍니다.

#include <iostream>

using namespace std;

int n;
int ary[21];
int num[20] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
int k;

void dfs(int dp,int count)
{
   int sum = 0;
   
   for (int i = 0;i < n;i++)
      sum += ary[i];

   if (sum == n)
   {
      for (int i = 0;i < dp;i++)
      {
         if(i == dp-1) cout<< ary[i];
         else cout << ary[i]<<"+";       

         
      }

      k++;
      cout << endl;
      return;
   }
   else if (sum > n) {
      return;
   }else{

      for (int i = count;i >= 0;i--)
      {//4부터 
         ary[dp] = num[i];
         dfs(dp+1,i);
         ary[dp] =0;
      }

   }


}

int main() {

   cin >> n;   
   dfs(0, n-2);  
   cout<<k<<endl;
   return 0;
}