Leetcode 216. Combination Sum III ||Backtracking

 Problem Link

In this problem, we just have to generate a sum  S using K numbers. The numbers could be in a range of (1-9) we only can take a number once for a combination.

Solution Idea: Backtracking.  

Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

class Solution { public: vector<vector<int> > ans; int k,n; void fun(int numberUsed, int num, int sum,vector<int>vec,int flag[]){ if(numberUsed == k){ if(sum==n){ ans.push_back(vec); } } else if(numberUsed<k){ if(sum<n){ for(int i=num+1;i<=9;i++){ if(flag[i]==0 && sum+i<=n){ vec.push_back(i); flag[i]=1; fun(numberUsed+1,i,sum+i,vec,flag); vec.pop_back(); flag[i]=0; } } } } } vector<vector<int>> combinationSum3(int kk, int nn) { k = kk; n = nn; int flag[10]; memset(flag,0,sizeof flag); vector<int>vec; fun(0,0,0,vec,flag); return ans; } };