• Source
    1. #include<bits/stdc++.h>
    2.  
    3. using namespace std;
    4.  
    5. map<vector<int>,int>mp;
    6.  
    7. vector<int>result;
    8.  
    9. bool flag;
    10.  
    11. int sum,t,n;
    12.  
    13. int arr[15];
    14.  
    15.  
    16. void backtracking(int start)
    17. {
    18. int i,j;
    19.  
    20. if(sum>t)
    21. {
    22. return;
    23. }
    24.  
    25. if(sum==t && !mp[result])
    26. {
    27. flag = true;
    28.  
    29. printf("%d",result[0]);
    30.  
    31. for(j=1; j<result.size(); j++)
    32. {
    33. printf("+%d",result[j]);
    34. }
    35.  
    36. puts("");
    37.  
    38. mp[result] = 1;
    39.  
    40. return;
    41. }
    42.  
    43. for(i=start; i<=n; i++ )
    44. {
    45.  
    46. sum += arr[i];
    47.  
    48. result.push_back(arr[i]);
    49.  
    50. backtracking(i+1);
    51.  
    52. sum -= arr[i];
    53.  
    54. result.pop_back();
    55.  
    56. }
    57. }
    58.  
    59.  
    60. int main()
    61. {
    62. int i;
    63.  
    64. while(scanf("%d%d",&t,&n)&&t&&n)
    65. {
    66. for(i=1; i<=n; i++)
    67. {
    68. scanf("%d",&arr[i]);
    69. }
    70.  
    71. sum = 0;
    72.  
    73. flag = false;
    74.  
    75. printf("Sums of %d:\n",t);
    76.  
    77. backtracking(1);
    78.  
    79. if(!flag)
    80. printf("NONE\n");
    81.  
    82. result.clear();
    83.  
    84. mp.clear();
    85. }
    86.  
    87. return 0;
    88. }