Leetcode 1641. Count Sorted Vowel Strings

Problem Link

We have to get the number of permutations we can have with using 5 vowels character in lexicographical order.

After every vowel character we can only take characters which are lexicographically equal or larger than it.
Suppose, we have a substring "aei" but we have to make the string size 4. But we can't take character "a" or "e", we forced to take character "i", "o", or "u".
For decrease the time complexity we used memoization technique with some extra memory space.

Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

class Solution { public: int memo[51][6]; int solve(int n,int i){ if(n==0){ return 1; } if(memo[n][i]!=0){ return memo[n][i]; } int forReturn = 0; for(int j=i;j<5;j++){ forReturn += solve(n-1,j); } memo[n][i] = forReturn; return memo[n][i]; } int countVowelStrings(int n) { return solve(n,0); } };

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; } };