<file_sep>
// Reverse a linked List 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseWrapper(ListNode *head,ListNode *&HEAD) {
        
        // Naive : copy list in another array
        //       : and change original list traversing reverse in array
        //       : time : theta(N) + space : theta(N)
        
        // Optimal : IBH method  
        //         : Hypothesis => reverseList(head) will return me the last pointer 
        //           of the reversed list and has head already set up
        //         : induction => connect current node wiht this last node and make last as current
        //         : base case => when we reach the last node or the nodes is empty 
        
        // Iterative Optimal : Take first on node 1 
        //                   : Take second on node 2
        //                   : preserve the next of node 2
        //                   : reverse the link between node 1 and node 2
        //                   : go on preserve and repeat the same process 
        //                   : at the end we return the head 
        
        // Base Case 
//         if(head == NULL||head->next==NULL) {
//             HEAD = head;
//             return head;
//         }
        
//         // Hypothesis
//         ListNode *last = reverseWrapper(head->next,HEAD);
        
//         // Induction
//         last->next = head;
//         head->next = NULL;
//         last=head;
        
//         return head;
        
    }
    ListNode* reverseList(ListNode* head) {
        // ListNode *HEAD;
        // reverseWrapper(head,HEAD);
        // return HEAD;
        
        
        // Better Recursive Solution taken from most votes
        
//         if(head==NULL||head->next==NULL)
//             return head;
        
//         ListNode *node = reverseList(head->next);
//         head->next->next=head;
//         head->next=NULL;
//         return node;
        
        //Iterative Solution { most optimal solution }
        if(head==NULL||head->next==NULL)
            return head;
        
        ListNode *prev = NULL;
        ListNode *curr = NULL;
        ListNode *Next = head;
        
        while(Next!=NULL) {
            
            curr=Next;
            Next=Next->next;
            curr->next=prev;
            prev=curr;
        
        }
        
        return curr;
        
    }
};<file_sep>

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {


    // we can also do it in iterative way which is optimal in space as compared to recursion    
    // For recursion
    //             - solving this using IBH method 


public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2,int carry = 0) {
        
        // Base Case 
        if(l1==NULL&&l2==NULL) {
            
            if(carry==0)
                return NULL;
            else 
            {
                ListNode *overFlow = new ListNode();
                overFlow->next = NULL;
                overFlow->val = carry;
                return overFlow;
            }

        }
        
        // Induction Step
        ListNode *currNode = new ListNode();
        
        int l1Value = (l1!=NULL) ? l1->val : 0;
        int l2Value = (l2!=NULL) ? l2->val : 0;
        
        int sum = l1Value + l2Value + carry;
        
        currNode->val = sum%10;
        
        carry = sum/10;
        
        ListNode *l1Next;
        ListNode *l2Next;
        
        if(l1==NULL)
            l1Next = NULL;
        else 
            l1Next = l1->next;
        
        if(l2==NULL)
            l2Next = NULL;
        else 
            l2Next = l2->next;
        
        // Hypothesis
        currNode->next = addTwoNumbers(l1Next,l2Next,carry);
        
        // Induction step
        return currNode;
        
    }

};<file_sep>
// Maximum Depth of binary tree

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        
        // Base Case -> if root is NULL the depth is 0
        if(root==NULL)
            return 0;
        
        // Recursive subProblem
        
        int lh = maxDepth(root->left);   // get the depth of the left sub tree
        int rh = maxDepth(root->right);  // get the depth of the right sub tree
        
        return max(lh,rh)+1;             // return the maximum of left depth and right depth + 1
          
    }
};<file_sep>
// Fibonacci numbers using dp and recursion

class Solution {
    
public:
    
    int CountFibN(int dp[],int n) {
        
        if(n==0||n==1)
            return n;
        
        if(dp[n-1]==-1)
            dp[n-1] = CountFibN(dp,n-1);
        if(dp[n-2]==-1)
            dp[n-2] = CountFibN(dp,n-2);
        
        return dp[n-1] + dp[n-2];
        
    }
    
    int fib(int n) {
        
        int dp[31];
        fill(dp,dp+31,-1);
        
        return CountFibN(dp,n);
        
    }
    
};<file_sep>

// Nth tribonacci number 

// Naive : Using normal formula like fibonacci number 

// optimal : use dp to optimize it


// optimal solution

int dp[38];

class Solution {
public:
    
    int T(int n)
    {
        
        if(n==0||n==1)
            return n;
        if(n==2)
            return 1;
        
        if(dp[n-3]==-1)
            dp[n-3] = T(n-3);
        
        if(dp[n-2]==-1)
            dp[n-2] = T(n-2);

        if(dp[n-1]==-1)
            dp[n-1] = T(n-1);
    
         return dp[n-3]+dp[n-2]+dp[n-1]; 
        
    }
    int tribonacci(int n) {
        
        int sum = 0;
        fill(dp,dp+38,-1);
        return T(n);

    }
    
};<file_sep>

//Binary Tree Tilt 

// Naive : O(N^2) - top down approach for each node calculate left sub tree node sum and same for right and maintian sum
// Optimal : O(N) - bottom up approach, maintian sum and node sum simultaneously

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    
    int GetSumOfTilts(TreeNode *root,int &sum) {
        
        // Base Case 
        
        if(root==NULL)
            return 0;
        
        // Intermediate Decision State
        
        int leftSubTreeNodeSum = GetSumOfTilts(root->left,sum);
        int rightSubTreeNodeSum = GetSumOfTilts(root->right,sum);
        
        sum = sum + abs(leftSubTreeNodeSum-rightSubTreeNodeSum);
        
        return (leftSubTreeNodeSum+rightSubTreeNodeSum+root->val);
        
    }
    int findTilt(TreeNode* root) {
        
        int sum = 0;
        GetSumOfTilts(root,sum);
        return sum;
    
    }
};<file_sep>bool dp[202][int(1e4+2)];

class Solution {
public:
    
    bool SubSetSum(vector<int>& nums,int sum,int n) {
        
        // writing recursive code and then memoize it and then go for tabulation -> method 1
        // this is similar to knapsack problem where given array is weight array 
        
        // and value arrays are ignored, and this problem can be solved using tabular 
        // derivation of the knapsack problem -> method 2
        
        
        // Method -> 1
            
//         // Base Case 
//         if(sum==0)
//             return true;
//         if(n==0)
//             return false;
        
//         if(dp[n][sum]!=-1)
//             return dp[n][sum];
        
//         // Choice Diagram
//         if(nums[n-1]<=sum)
//            return dp[n][sum] = (SubSetSum(nums,sum-nums[n-1],n-1)||SubSetSum(nums,sum,n-1));
//         else 
//             return dp[n][sum] = SubSetSum(nums,sum,n-1);
        
        
        // Method -> 2 { Observed that it's knapsack variation}
        
        // initializtion of method 2
        for(int j=0;j<sum+1;j++)
            dp[0][j]=false;
        for(int i=0;i<nums.size()+1;i++)
            dp[i][0]=true;
        
        for(int i=1;i<n+1;i++){
            for(int j=1;j<sum+1;j++){
                if(nums[i-1]<=j){
                    dp[i][j] = dp[i-1][j-nums[i-1]]||dp[i-1][j];
                }
                else
                    dp[i][j] = dp[i-1][j];
            }
        }
        
        return dp[n][sum];
        
    }
    bool canPartition(vector<int>& nums) {
        
        // this is the question on equal sum partitation 
        // means there are two subsets/paritation which has equal sum in the array
        // also there sum add to total array sum
        // thus since those two subset have equal sum the array sum should be even 
        // for the partitaion to exist
        
        // if the sum is even we simply need to check if there exist a subset 
        // with sum equal to sum/2 in the array or not 
        
        // for method 1, memoization
        // memset(dp,-1,sizeof(dp));

        
        int sum = 0;
        
        for(int i=0;i<nums.size();i++)
            sum+=nums[i];
        
        if(sum%2 != 0) 
            return false;
        else
            return SubSetSum(nums,sum/2,nums.size());
        
    }
};<file_sep>

// swap nodes in pair 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
    
public:
    
    ListNode* swapPairs(ListNode* head) {
        
        // We can solve this using iterative method -> theta(N)
        // We can solve this using recursion as well -> theta(N) + theta(N)
        
        // changing links will be better than swapping !
        
        // 1] Assuming a hypothesis that swapPairs(ListNode*) will return me the head pointer pointing to n-2 nodes list
        // 2] In the inductio step, we can change the links of the current two nodes and return the head
        // 3] Base case will, if we have head as NULL [size if even] we returning NULL if head not NULL [size is odd] return head
        
        // try out a tail recursive solution 
        
        // Base Case 
        if(head == NULL)     // when size is even
            return NULL;
        
        if(head->next==NULL) // when size is odd
            return head;
        
        // hypothesis
        ListNode *nextHead = swapPairs(head->next->next);
        ListNode *newHead = head->next;
        
        head->next->next = head;
        head->next = nextHead;
        
        return newHead;
        
    }
    
};<file_sep>
// Reorder List 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    
    ListNode* reorderListHelper(bool &isEven,ListNode *head,ListNode *&nextHalf,int &countNode) {

        
        if(countNode==0) {
            
            if(isEven) {
                
                nextHalf = head->next->next;
                head->next->next = NULL;
                return head;
                
            }
            else {
                
                nextHalf = head->next->next->next;
                head->next->next->next = head->next;
                ListNode *temp = head->next;
                head->next = head->next->next;
                temp->next = NULL;
                return head;
                
            }
            
        }
        
        ListNode *newHead = reorderListHelper(isEven,head->next,nextHalf,--countNode);
        
        head->next=nextHalf;
        ListNode *temp = nextHalf->next;
        nextHalf->next = newHead;
        nextHalf=temp;
        
        return head;
        
    }
    
    void reorderList(ListNode* head) {
        
        // Naive : take extra array and copy all elements into it 
        //       : then we can take required elements one by one 
        
        // optimal 1 : If it's ok to change the original linked list it self
        //           : count the nodes in the linked list -> theta(N)
        //           : move ahead by ceil(n/2) + 1 in the list  -> theta(N/2)
        //           : make the next of the current after moving as null
        //           : reverse the next part of the linked list  -> Theta(N/2)
        //           : and keep connecting one by one  -> Theta(N/2)
        //           : time is theta(N) space is O(1)
        
        // optimal 2 : Can we use recursion ?
        //           : then we can solve it recursively 
        //           : say a function fun() returns us the head of the ordered internal list
        //           : then the just have to change the links of the current two nodes 
        //           : time complexity will be Theta(N) {N/2 less iterations as previous}, space is theta(N/2)
        
            
        if(head == NULL)
            return;
        if(head->next == NULL)
            return;
        
        ListNode *curr = head;
        ListNode *nextHalf = NULL;
        
        // counting the nodes in the list 
        int countNode = 0;
        
        while(curr!=NULL)
        {
            countNode++;
            curr=curr->next;
        }
        
        bool isEven = ((countNode%2)==0);
        
        // reordering the list 
        countNode/=2;
        countNode--;
        reorderListHelper(isEven,head,nextHalf,countNode);
        
        return;
        
    }
    
};<file_sep>
// Power of 2 

class Solution {
public:
    bool isPowerOfTwo(int n) {
        
        // Naive : take mod
        //       : keep dividing the number by 2 if we get odd number except 1 then it's not power of 2
        //       : time : O(logN)
        //       : we can solve this using both recursive and iterative versions 
        
        // Optimal : if number is power of 2 then it has only 1 bit set in it's binary
        //         : so total set bits in number should be 1
        //         : we can iterate on bits in O(logN)
        //         : to optimize this we can use brian kerningam algorithm
        
        // Most optimal : n&(n-1) should be 0 brian kerningam algorithm
        
        // recursive solution 
        
        // Base Case 

//         if(n==1)
//             return true;
        
//         if(n<=0||n%2==1)
//             return false;
        
//         return isPowerOfTwo(n/2);
        
        
        // Most optimal 
        
        return (!(n<=0)&&((n&(n-1))==0));
        
            
    }
};<file_sep>    
    
    // Convert BST to inorder tree { increasing order search tree }
    
    void increasingBSTwrapper(TreeNode *root,TreeNode *&prev,TreeNode *&newRoot) {
        
        // Naive : Generate Inorder traversal list and then create a tree form that 
        //       : time : theta(N), space : theta(N) {but more than optimal}
        
        // Optimal : Traverse in Inorder way, and generate change the same tree, using previous pointer and root pointer
        
        // Base case 
        if(root==NULL)
            return;
        if(prev==NULL && root->left==NULL) {
            prev = root;
            newRoot = prev;
        }
        
        // Inorder traversal 
        increasingBSTwrapper(root->left,prev,newRoot);
        
        if(prev!=root) {
            prev->left=NULL;
            prev->right=root;
            root->left=NULL;
            prev=root;
        }
        
        increasingBSTwrapper(root->right,prev,newRoot);
        
        
    }
    TreeNode* increasingBST(TreeNode* root) {
        
        TreeNode *newRoot;
        TreeNode *prev = NULL;
        increasingBSTwrapper(root,prev,newRoot);
        return newRoot;
        
    }
      
    // Actual Solution :  Best Solution
    //     TreeNode* increasingBST(TreeNode* root, TreeNode* tail = NULL) {
    //     if (!root) return tail;
    //     TreeNode* res = increasingBST(root->left, root);
    //     root->left = NULL;
    //     root->right = increasingBST(root->right, tail);
    //     return res;
    // }<file_sep>

// Finding power x^n where n and x can be negative


class Solution {
public:
    
    double pow(double x,long long int n) {   
        
        // pow(x,n) = pow(x,n/2)*pow(x,n/2)   if n is even 
        //            pow(x,n/2)*pow(x,n/2)*x if n is odd
        
        if(n==0)
            return 1.0;
        if(n==1)
            return x;
        
        double temp = pow(x,n/2);
        temp*=temp;
        
        if( (n%2) == 1 )
            return temp*x;
        else 
            return temp;
    
    }
    double myPow(double x, int n) {
    
        long long int n1 = n;
        
        if(n<0){
            return (1.0/pow(x,abs(n1)));
        }
        else 
            return pow(x,n1);
        
    }
};<file_sep>
//Merge Two Sorted Lists

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    
    ListNode* MergeHelper(ListNode *l1,ListNode *l2,ListNode *Head,ListNode *prev = NULL) {
        
        // Tail Recursive Solution
        
        //base case 
        
        if(l1==NULL) {
            prev->next = l2;
            return Head;
        }
        else if(l2==NULL) {
            prev->next = l1;
            return Head;
        }
        
        //Dealing intermediate decision state
        
        if(l1->val <= l2->val) {
            
            if(prev==NULL) {
                Head = l1;
                prev = Head;
            }
            else {
                prev->next = l1;
                prev = prev->next;
            }
            
            return MergeHelper(l1->next,l2,Head,prev);
            
        }
        else {
            
            if(prev==NULL) {
                Head = l2;
                prev = Head;
            }
            else {
                prev->next = l2;
                prev = prev->next;
            }
            
            return MergeHelper(l1,l2->next,Head,prev);
            
        }
        
    }
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        
        // Non Tail Recursive Solution
        
        //Base Case
        if(l1==NULL)
            return l2;
        else if(l2==NULL)
            return l1;
        
        // Intermediate decision state
        if(l1->val <= l2->val) {
            l1->next = mergeTwoLists(l1->next,l2);
            return l1;
        }
        else {
            l2->next = mergeTwoLists(l1,l2->next);
            return l2;
        }
        
    }
};<file_sep>
// Range Sum in a BST, VVIMP

        
        // Naive : Since it's a BST we can take the inorder into an array which will be sorted, and find the sum
        //       : time : Theta(N), space : O(N)
        
        // optimal : take the inorder traversal and which ever number lies in [low, high] we take it into the sum
        //         : time : theta(N), space: O(height)
        
        // more optimal : since it's a BST so we can skip some traversals 
        //              : if root->val lies in range then we call on both sides
        //              : else if root->val is more than high then call only on left side 
        //              : else if root->val is less than low then we call onlhy on right side 
        //              : time complexity : O(N), space : O(height)
        
        
        
        //1]  optimal
        // Base Case 
//         if(root==NULL)
//             return 0;
        
//         // inorder traversal
//         int leftPossibleNodeVal = rangeSumBST(root->left,low,high);
        
//         if( ( root->val >= low ) && ( root->val <= high ) ) {
//             leftPossibleNodeVal += root->val;
//         }
        
//         int rightPossibleNodeVal = rangeSumBST(root->right,low,high);
        
//         return (leftPossibleNodeVal+rightPossibleNodeVal);
        
        // 2] most optimal
        
        if(root==NULL)
            return 0;
        
        if(root->val >= low && root->val <=high ){
            return (rangeSumBST(root->left,low,high) + root->val + rangeSumBST(root->right,low,high));
        }
        else if(root->val<low){
            return rangeSumBST(root->right,low,high);
        }
        else {
            return rangeSumBST(root->left,low,high);
        }<file_sep>
// Balanced Binary Tree

// Naive : O(N^2) call height for each node and compare 

// Optimal : O(N)


// Optimal Solution

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    
    int height(TreeNode *root) {
        
        //base case
        if(root==NULL)
            return 0;
        
        //intermediate decision state
        
        int lh = height(root->left);
        int rh = height(root->right);
        
        int diff = abs(lh-rh);
        
        if(lh==-1||rh==-1||diff>1)
            return -1;
        else 
            return max(lh,rh) + 1;
        
    }
    
    bool isBalanced(TreeNode* root) {
        
        int h = height(root);
        
        if(h==-1)
            return false;
        else 
            return true;
        
    }
};<file_sep>    
    

    // Minimum distance between two nodes of a BST
    
        // Naive : for every node in the tree, we traverse the tree and find the difference and maintain the minimum
        //       : time : theta(N^2), space theta(N)
        
        // Optimal : Traverse in inorder way {will be sorted list} and take adjacent differences of sorted list
        //         : time : theta(N), space theta(N)
        
        
        // Inorder : first traverse the left sub tree then come to root then traverse the right sub tree
    
    
    
    
    
    
    void minDiffInBSTwrapper(TreeNode *root,int &minDiff,TreeNode *&prev) {
        
        //base case 
        
        if(root==NULL)
            return;
        
        // important part of base case to ensure that prev is correctly assigned
        if(prev==NULL && root->left==NULL)
            prev = root;
        
        
        // traversing the left sub tree making sure that prev is on correct node
        minDiffInBSTwrapper(root->left,minDiff,prev);
        
        // coming to root and then taking the minDiff, considering extra case
        if(root!=prev)
            minDiff = min(abs(root->val - prev->val),minDiff);
        prev = root;
        
        // traversing the right sub tree making sure that root was at correct node 
        minDiffInBSTwrapper(root->right,minDiff,prev);
        
        
    }
    int minDiffInBST(TreeNode* root) {
        
        int minDiff = INT_MAX;
        TreeNode *prev = NULL;
        minDiffInBSTwrapper(root,minDiff,prev);
        return minDiff;
        
    }<file_sep>

// Delete Nodes with a given value in linked list 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val,ListNode *prev=NULL,ListNode *HEAD = NULL) {
        
        // Iterative : maintain a previous pointer and delete current and change links theta(N) + O(1)
        // Recursive : IBH method 
        
        // Base case 
        if(head==NULL)
            return HEAD;
        
        // Hypothesis 
        
//         ListNode *getHead = removeElements(head->next,val);
        
//         // Induction Step
        
//         if(head->val==val) {
//             head->next=NULL;
//             delete head;
//             head = getHead;
//         }
//         else
//             head->next = getHead;

_______________________________________________________________________________________


           Trying tail recursive method 
//         ListNode *nextNode=head->next;
            
//         if(head->val == val){
            
//             if(prev==NULL)
//             {
                
//                 nextNode = head->next;
//                 HEAD = nextNode;
//                 delete head;
                
//             }
//             else {
                
//                 prev->next=head->next;
//                 head->next=NULL;
//                 delete head;
//                 nextNode = prev->next;
                
//             }
            
//         }
//         else {
//             if(prev==NULL)
//                 HEAD = head;
//             prev=head;
//         }
        
//         return removeElements(nextNode,val,prev,HEAD);
    
    }
    
};<file_sep># LeetCode
This Repo has the questions of LeetCode that I have solved

currently working on recursion
<file_sep>

// Check Iterative version also 
// this can be solved using recursion tree method, as there are multiple choices and decisions 

class Solution {
public:
    void getCombinations(string source,int index,string &digits,vector<string> &digitsString,vector<string> &result,string curr = "") {
        
        // O(4^n) max(n) = 4; { ie : assume the loop as 4 function calls }
        
        if(index==digits.length()) {
            
            result.push_back(curr);
            return;
            
        }
        
        for(int i=0;i<source.length();i++) {
            
            string nextSource = index+1<digits.length() ? digitsString[digits[index+1]-50] : "" ;

            getCombinations(nextSource,index+1,digits,digitsString,result,curr + source[i]);
            
        }
        
    }
    vector<string> letterCombinations(string digits) {
        
        if(digits.length()==0)
            return {};
        
        vector<string> digitsString(8);
        
        digitsString[0]="abc";
        digitsString[1]="def";
        digitsString[2]="ghi";
        digitsString[3]="jkl";
        digitsString[4]="mno";
        digitsString[5]="pqrs";
        digitsString[6]="tuv";
        digitsString[7]="wxyz";
        
        vector<string> result;
            
        string source = digitsString[digits[0]-50];
            
        getCombinations(source,0,digits,digitsString,result);
        
        return result;
        
    }
};<file_sep>

class Solution {
public:
    
    
    // Naive : Useing BIT magic to generate subsets O(n*2^n)
    // Optimal: Using recursion and maintaining xor and sum
    // most optimal : checkfrom discussion
    
    
    int subsetXORSum(vector<int>& nums) 
    {
        
        int n = nums.size();
        int sum = 0;
        
        for(int curPattern=0;curPattern<pow(2,n);curPattern++){
            
            int curXOR = 0;
            for(int j=0;j<n;j++) {
                if((1<<j)&curPattern){
                    curXOR = curXOR^nums[j];
                }
            }
            sum+=curXOR;
        }
        
        return sum;
        
    }
};