[LeetCode] – Recursion/ dp- Decode Ways

Problem:

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

Method 1: by DP

Consider the current character and the previous character.

Code for method 1:

// dp
public class Solution {
    public int numDecodings(String s) {
        if (s.length() == 0) return 0;
        if (s.charAt(0) == '0') return 0;
        // at least one elements here, and not 0;
        int[] dp = new int[s.length()+1];
        dp[0] = 1;
        dp[1] = 1;
        
        for (int i = 2; i <= s.length(); i++){
        
            if(s.charAt(i - 2) > '2' && s.charAt(i-1) == '0'){
                dp[i] = 0;
            }else if (s.charAt(i - 2) > '2' && s.charAt(i-1) != '0'){
                dp[i] = dp[i-1];
            }else if (s.charAt(i-2) == '2' && s.charAt(i-1) >= '1' &&s.charAt(i-1) <= '6' ){
                dp[i] = dp[i-1]+dp[i-2];
            }else if (s.charAt(i-2) == '2' && s.charAt(i-1) == '0'){
                dp[i] = dp[i-2];
            }else if (s.charAt(i-2) == '2' && s.charAt(i-1) >= '7' ){
                dp[i] = dp[i-1];
            }else if (s.charAt(i-2) == '1' && s.charAt(i-1) != '0'){
                dp[i] = dp[i-1]+dp[i-2];
            }else if (s.charAt(i-2) == '1' && s.charAt(i-1) == '0'){
                 dp[i] = dp[i-2];
            }else if (s.charAt(i-2) == '0' && s.charAt(i-1) != '0'){
                dp[i] = dp[i-1];
            }else{
                dp[i] = 0;
            }
        }
        return dp[s.length()];
    }
}

Another more beautiful code for method 1:

public int numDecodings(String s) {  
        if (s.length()==0||s==null||s=="0") 
            return 0; 

        int[] dp = new int[s.length()+1];  
        dp[0] = 1;  
        
        if (isValid(s.substring(0,1)))
            dp[1] = 1;  
        else 
            dp[1] = 0; 
        
        for(int i=2; i<=s.length();i++){  
            if (isValid(s.substring(i-1,i)))  
                dp[i] += dp[i-1];  
            if (isValid(s.substring(i-2,i)))  
                dp[i] += dp[i-2];  
        }  
        return dp[s.length()];  
    }  
      
    public boolean isValid(String s){  
        if (s.charAt(0)=='0') 
            return false;  
        int code = Integer.parseInt(s);  
        return code>=1 && code<=26;  
    }

Method 2: by Recursion. Too slow.

// by recursive
public class Solution {
    public int numDecodings(String s) {
        int len = s.length();
        if (len == 0) return 0;
        if (len == 1 ){
            if (isValid(s.substring(0,1))) return 1;
            else return 0;
        }
        int res = 0;
        // at least have two elements here.
        if (isValid(s.substring(len-1,len))) res += numDecodings(s.substring(0,len-1));
        if (isValid(s.substring(len-2, len))) res += numDecodings(s.substring(0,len-2));

        return res;
    }
    
    public boolean isValid (String s){
        if (s.length() == 0 ) return false;
        int i = Integer.parseInt(s);
        if ( i >= 1 && i <= 26 ) return true;
        else return false;
    }
}

[LeetCode] – Recursion / DP / Greedy – Wildcard Matching

Problem:

Implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

Reference: http://shmilyaw-hotmail-com.iteye.com/blog/2154716

Method 1:  Greedy

str: the original string we need to examine

pattern: the string with wildcard

s: the cursor in str

p: the cursor in p

StarIdx: the place of the last encountered * (Initialize as -1)

match: the place in str, when p encountered a *

• We go through every char in str
  • If p and s match, p++, s++
  • If p and s do not match, and p encounter a *: remember the current place of p and s in ‘StarIdx’ and ‘match’. Then, p++l .
  • If p and s do not match, and p does not encounter a *, but StarIdx is not  -1: update p as StarIdx+1, update match as match+1, update s as match.
  • If p and s do not match, and p does not currently at a *, and p does not ever encountered an * before, we can decide, the two string do not match. Return false;
• After checking every char in str, we need to check if there are still char left in p. We only allow *.

Code:

public class Solution {
    public boolean isMatch(String str, String pattern) {
        int s = 0; // cursor for traversal in str.
        int p = 0; // cursor for traversal in pattern.
        int starIdx = -1; // once we found a star, we want to record the place of the star.
        int match = 0; // once we found a star, we want to start to match the rest of pattern with str, starting from match; this is for remembering the place where we need to start.
        
        // we check and match every char for str.
        while (s < str.length()){
            // 1. case 1: we are not currently at any *, 
            if (p < pattern.length() && (pattern.charAt(p) == str.charAt(s) || pattern.charAt(p) == '?')){
                p++;
                s++;
            }// 2. case 2: we are currently at a '*'
            else if (p < pattern.length() && pattern.charAt(p) == '*' ){
                starIdx = p;
                p++;
                match = s;
            } // 3. case 3: they do not match, we do not currently at a *, but the last matched is a *
            else if (starIdx != -1){
                match++;
                s = match;
                p = starIdx + 1;
            } // 4. case 4: they do not match, do not currently at a *, and last matched is not a *, then the answer is false;
            else{
                return false;
            }
        }
        // when we finish matching all characters in str, is pattern also finished? we could only allow '*' at the rest of pattern
        while (p < pattern.length() && pattern.charAt(p) == '*')
        p++;
  
        return p == pattern.length();
    }
}

Method 2:

We could use recursive method. Recursive: we just check one step. Iterative: we use while to check all steps.

• Parameters:
  • String str: the original string
  • String pattern: the pattern string
  • int l: the cursor in original string
  • int r: the cursor in pattern string
• Function: starting from l and r, the left part do match.
• Base Case: If r reaches the end of str, we need to check if l also reaches the end of pattern. If so, match.
• Reduction: check the current char in pattern string
  • If regular, just increase l and r by 1;
  • If *, first, go to the last *, and then check if match. (we have to use while loop to find the correct starting point.)

Code for method 2:

public class Solution {
    public boolean isMatch(String s, String p) {
        return helper(s,p,0,0);
        
    }
    
    
    boolean helper(String s, String p, int l, int r) {
           if(r == p.length()) return l == s.length();
           
           if(p.charAt(r) == '*') {
                 while(r < p.length() && p.charAt(r) == '*') r++;   // Move the index at p to a non-start char.
                 while(l < s.length()) {
                     if(helper(s, p, l, r)) return true; // Find one match, return true.
                      l++; // Try the next one.
                  }
                 return helper(s, p, l, r);
            }else if(l < s.length() && (p.charAt(r) == '?' || s.charAt(l) == p.charAt(r))){
                return helper(s, p, l + 1, r + 1);
            }else{
                 return false;
            }
    }

}

Method 3:

However, the recursive method is too slow and we need to have a quicker speed. So we try to solve it by DP.

1. Regular case: if two chars are the same, or p is ‘?’, then go to check dp[i-1][j-1]

2. Special case: when p is ‘*’, we need to check dp[i-1][j-1] for every i>0. If there is one true, then the answer is true.

Code for method 3:

// use DP
public class Solution {
    public boolean isMatch(String s, String p) {
        int width = s.length();
        int height = p.length();
        
        boolean[][] dp = new boolean[width + 1][height + 1];
        dp[0][0] = true;
        
        for (int i = 1; i <= width; i++){
            for (int j = 1; j <= height; j++){
                if (s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1) == '?'){
                    dp[i][j] = dp[i-1][j-1];
                }else if (p.charAt(j-1) == '*'){
                    int cur = i;
                    while (cur > 0){
                        if (dp[cur-1][j-1]){
                            dp[i][j]= true;
                            break;
                        }
                        cur--;
                    }
                }
            }
        }
        
        return dp[width][height];
    }
}

[LeetCode] – Recursion / dp – Interleaving String

Problem:

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

Method 1: (by recursion)

• Recursion method is too slow, and can not pass the checker. But is still a way to approach the problem.
• Several things to remember:
  • We could start from s1 or s2, not necessarily s1.
  • If s1 is null, s2 is null, only when s3 is also null, we get true. Otherwise false;
  • If we go through s1 and s3, try to cut the same part and stop until we reach something different, we might be wrong. Because there may be same sub-string in s2, and the actual choice is s2. So we have to check the answer every time we advance by 1 in s1 and s3. But don’t change s3 and s1.

Code for method 1:

// Recursion
public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        return helper(s1, s2, s3) | helper(s2, s1, s3);

    }
    public boolean helper(String s1, String s2, String s3){
        // helper method make sure s1 goes first.
        // Base cases: (make sure that s1 is not null) 
        if (s1.length() == 0 && s2.length() == 0 && s3.length() == 0) return true;
        if (s1.length() == 0 && s2.length() != 0) return false;
       
        int i = 0;
        while (i < s1.length() && i < s3.length() && s1.charAt(i) == s3.charAt(i)){
            i++;
            // check if already true; and do not change s1 and s3.
            if (helper(s2,s1.substring(i),s3.substring(i))) return true;
        }
        if (i == 0) return false;
        s1 = s1.substring(i);
        s3 = s3.substring(i);
        return helper(s2,s1,s3);
    }
}

Method 2: (by dp)

• Remember: “When you see string problem that is about subsequence or matching, dynamic programming method should come to your mind naturally. ”
• dp[i][j] means if the i+j chars in s3 are composed of i chars in s1, and j chars in s2. We just have to check the new added char every time we increase the dp’s dimension.
• Don’t forget to kick out the case that s3 does not include all the chars in s1 and s2.
• One trick for dp: string index is one less than dp matrix index.

Code for method 2:

// by dp
public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int height = s1.length();
        int width = s2.length();
        // consider special case: s3 does not include all the elements in s1 and s2.
        if (s3.length() != height+width) return false;
        boolean[][] dp = new boolean[height+1][width+1];
        
        dp[0][0] = true;
        for (int i = 1; i <= height; i++){
            if (s1.charAt(i-1) == s3.charAt(i-1) && dp[i-1][0] ) dp[i][0] = true;
        }
        
        for (int j = 1;j <= width; j++){
            if (s2.charAt(j-1) == s3.charAt(j-1) && dp[0][j-1] ) dp[0][j] = true;
        }
        
        for (int i = 1; i <= height; i++){
            for (int j = 1; j <= width; j++){
                if ((s3.charAt(i+j-1) == s2.charAt(j-1) && dp[i][j-1]) || (s3.charAt(i+j-1) == s1.charAt(i-1) && dp[i-1][j])){
                     dp[i][j] = true;
                }
            }
        }
        return dp[height][width];
    }
}

[LeetCode] – Recursion/DP- Regular Expression Matching

Problem:

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

Method 1(Recursion):

1. Make sure we totally understand the question.

• “.” is easy, just representing a single char.
• “x*” represent 0 or more x, e.g., “”,”x”,”xx”,”xxx”,”xxxxxx”…

2. We use recursive method. Check if the first part is match or not, if yes, check the rest of the regular expression.

• Reduction:
  • If next char is not “*”, we just compare this current char, and reduce both the length of s and p by 1.
  • If next char is “*”:
    • If the current char is the same, reduce s by 1 and check again. Until the current char is different.  — Not accurate! Consider: “aaa” and “a*a”. So every time before we reduce p by 1, we have to check if they match. This check must to be placed before we reduce p by 1, since we could have the case: s = abc   p = .*abc
    • If the current char is different, reduce p by 2.
• Base case: As reduction reduces length by 1 or 2 every time, we need to consider finally when length == 0 or length == 1.
  • If p.length() == 0, check if s.length() is also 0.
  • If p.length() == 1, check if s.length() is also 1 and the char match or not.
• A detail: s.subString(l), could return null if l is the length of s.
• A detail: always check s.length

Code for method 1:

public class Solution {
    public boolean isMatch(String s, String p) {
        if (p.length() == 0){
            return s.length() == 0;
        }
        if (p.length() == 1){
            return s.length() == 1 && (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.');
        }
        
        // Now, we make sure that p has at least 2 chars.
        if (p.charAt(1) != '*'){
            if (s.length() == 0) return false;
            else return  (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.')&& isMatch(s.substring(1), p.substring(1));

        }else{ // p.charAt(1) == '*''
            while (s.length() > 0 && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.')){
                if (isMatch(s,p.substring(2))) return true;  // this has to be before s= s.substring(1), to deal with the case: s=abc  p = .*abc
                
                s = s.substring(1);
                
                
            }
            return isMatch(s, p.substring(2));
        }
        
    }
}

Method 2(DP):

1. Create a 2-d matrix, with width as p.length(), height as s.length()

2. Consider an important question: what does ‘a*’ mean?

• Case1: Means nothing, we can’t totally delete ‘a*’. — dp[i][j] = dp[i][j-2]
• Case 2: Means some numbers of ‘a’ in s. — dp[i][j]= dp[i-1][j] (Try to change this case to case 1.)

3. Pay attention to the initialization.  We want to make sure when s is null and p is ‘a*’, we get a ‘true’. This is a base case for Case 1.

Code for method 2:

// Use dp
public class Solution {
    public boolean isMatch(String s, String p) {
       boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
      dp[0][0] = true;
      
      for (int i = 1; i <= p.length(); i++){
          if (p.charAt(i-1) == '*') dp[0][i] = dp[0][i-2];
      }
      
      for (int i = 1; i <= s.length(); i++){
          for (int j = 1; j <= p.length(); j++){
              char pChar = p.charAt(j-1);
              char sChar = s.charAt(i-1);
              
              if (pChar != '*'){
                  if (pChar == sChar || pChar == '.'){
                      dp[i][j] = dp[i-1][j-1];
                  }else{
                      dp[i][j] = false;
                  }
              }else{
                  if (p.charAt(j-2) != sChar && p.charAt(j-2) != '.'){
                      dp[i][j] = dp[i][j-2];
                  }else{
                      dp[i][j] = dp[i-1][j]|dp[i][j-2];
                  }
              }
          }
      }
      
      
      return dp[s.length()][p.length()];
      
    }
}

[LeetCode] – Recursion – Flatten Binary Tree to Linked List

Problem:

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

Hints:If you notice carefully in the flattened tree, each node’s right child points to the next node of a pre-order traversal.

Method 1： 

Iterative.

Whenever you encounter a node, if it has left-sub-node, then you insert all the left-sub-tree into the right branch. Append all the left right subtree to the most right sub-nodes.

Please make sure to update the left-tree reference to null once moved it to the right.

Code for method 1:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;
        
        TreeNode temp = root;
        while (temp != null){
           if (temp.left == null){
               temp = temp.right;
           }else{ // temp.left != null
               // find the most right sub node in the left-sub-tree.
               TreeNode right_most = temp.left;
               while (right_most.right != null){
                   right_most = right_most.right;
                }
               right_most.right = temp.right;
               temp.right = temp.left;
               temp.left = null;  // this is important for in-place list operation. Java is "pass by value", when you move left sub tree to the right, you just copy the reference, and the left sub tree still exist in the original place, which is not what we want.
               temp = temp.right;
           }
        }
        
    }
}

Method 2:

Recursive. 

Use pre-oder traversal.

• Define a field, recording the last visited element, so that we don’t lose track of the list when we update references. This field has to be out of the method.
• Base case: if the current node is null, return;
• Reduction: put the current node at lastvisit.right, and the current node becomes the new lastvisit node. Save the current.right node as savedRight, since it’s going to be changed in the next level of recursion. Then, call the method for current.left. After that, call the method for savedRight.

Code for method 2:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    // We have to define a separete field to record which is our last vist node
    public TreeNode lastvisit = null; 
    public void flatten(TreeNode root) {
       if (root == null) return;
         TreeNode savedRight = root.right;  // have to save right, since right is going to be changed.
         if (lastvisit != null){
             lastvisit.left = null;
             lastvisit.right = root;
         }
         lastvisit = root;
         flatten(root.left);
         flatten(savedRight);
    }
}

 

[LeetCode] – Recursion – Convert Sorted List to Binary Search Tree

Problem:

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

Method:

Use recursive method, just as the problem: “Convert Sorted Array to Binary Search Tree “. However, in order to access each element by index in constant time, we need to first put all the nodes of the list to an ArrayList. (ArrayList is 0-based indexing.)

Please note ArrayList use “size()” to get the number of element in the ArrayList.

Code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; next = null; }
 * }
 */
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        while (head != null){
            list.add(head.val);
            head = head.next;
        }
        return helper(list, 0, list.size()-1);
    }
    public TreeNode helper(ArrayList<Integer> list, int start, int end){
        if (start > end){
            return null;
        }else{
            TreeNode temp = new TreeNode(list.get((start+end)/2));
            temp.left = helper(list, start, (start+end)/2 - 1);
            temp.right = helper(list, (start+end)/2+1, end);
            return temp;
        }
    }
}

[LeetCode] – Recursion – Convert Sorted Array to Binary Search Tree

Problem:

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

Method:

We use recursive method:

• Method parameters:  array, starting index, ending index;
• Method return type: TreeNode
• Base case: if starting index > ending index, return null
• Get the median as the root. For the left half array: call the method and append to the root.left. For the right half array: call the method and append to the root.right. Return root.

Code:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode sortedArrayToBST(int[] num) {
       return helper(num, 0, num.length-1);
        
    }
    public TreeNode helper(int[] num, int start, int end){
        // start is the starting index, and end is the ending index;
        // First, get the median element as the root node
        if(start <= end){
             TreeNode root = new TreeNode(num[(start+end)/2]);
             root.left = helper(num, start, (start + end)/2 - 1);
             root.right = helper(num, (start + end)/2 + 1, end);
             return root;
        }else {
            return null;
        }
    } 
}

[LeetCode] – Recursion – Binary Tree Inorder Traversal

Problem:

Given a binary tree, return the inorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

OJ’s Binary Tree Serialization:The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.

Here’s an example:

   1
  / \
 2   3
    /
   4
    \
     5

The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

Method 1：

By recursion.

Base case: if null, return;

Reduction: Do the method for the left-sub-tree, and then add the current node, and then do the method for the right-sub-tree.

Please note: use ArrayList to store the traversal result.

Code for method 1:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        // base case:
        if (root == null) return res;
        // reduction:
        ArrayList<Integer> res_left = (ArrayList<Integer>)inorderTraversal(root.left);// important to case variable type
        res.addAll(res_left);
        res.add(root.val);
        ArrayList<Integer> res_right = (ArrayList<Integer>)inorderTraversal(root.right);
        res.addAll(res_right);
        return res;
    }
}

Method 2:

If we don’t want to use recursive method, we could use a stack to implement an iterative method.

Temp is pointed to head. No nodes in the stack at the beginning.

• While condition: Stack is not empty or temp is not null
• Inside the while loop: if temp is not null, push it to the stack, go to its left child; if temp is null, pop one node, visit it, and go to its right child.

Code for method 2:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        
        ArrayList<Integer> res  = new ArrayList<Integer>();
        if (root == null) return res;
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode temp = root;
        
        while (!stack.isEmpty() || temp != null){  // this condition is very important.
            if (temp != null){
                stack.push(temp);
                temp = temp.left;
            }else{
                temp = stack.pop();
                res.add(temp.val);
                temp = temp.right;
            }
        }
        return res;
    }
}

[LeetCode] – Recursion – Subsets II

Problem:

Given a collection of integers that might contain duplicates, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Method:

Please see the method for problem “Subsets”. The only difference is we have to check if there is already exist the same subset when insert a new subset.

Code:

public class Solution {
    public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
         ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> item = new ArrayList<Integer>();
        
        // Define base case:
        if (num.length == 0){  // empty set
            res.add(item);
            return res;
        }
        // find the max value in S, and create a new array without this value
        int max = Integer.MIN_VALUE;
        int index = -1;
        int[] newS = new int[num.length - 1];
        
        for (int i = 0; i < num.length; i ++){
            if (num[i] > max){
                max = num[i];
                index = i;
            }
        }
        
        int j = 0;
        
        for (j = 0; j < index; j++){
            newS[j] = num[j];
        }
        
        for (int m = index + 1; m < num.length; m ++){
            newS[j] = num[m];
            j++;
        }
        // get the result for the new array
        ArrayList<ArrayList<Integer>> pre_res = subsetsWithDup(newS);
        res.addAll(pre_res);
        
        for ( ArrayList<Integer> p: pre_res){
            ArrayList<Integer> new_item = new ArrayList<Integer>();
            new_item.addAll(p);
            new_item.add(max);
            if (! res.contains(new_item)){  // Pay atten to this !!!! Difference!!!
                res.add(new_item);
            }
            
        }
        return res;
    }
}

[LeetCode] – Recursion – Subsets

Problem:

Given a set of distinct integers, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Method:

We need to use recursive method.

1. Base case: if S is null, then return a set with an empty set in it.

2. Reduction: Find the maximum element in the original set. Remove the max element. For the rest of the set, call the method and put all the subsets as part of the results. Besides these subsets, we need to add max element to each of the subset and make it as a new subset.

Please note, use ‘ArrayList’. ‘add’ put element into the ArrayList. ‘addAll’ put all the element into the ArrayList.

Code:

public class Solution {
    public ArrayList<ArrayList<Integer>> subsets(int[] S) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> item = new ArrayList<Integer>();
        
        // Define base case:
        if (S.length == 0){  // empty set
            res.add(item);
            return res;
        }
        // find the max value in S, and create a new array without this value
        int max = Integer.MIN_VALUE;
        int index = -1;
        int[] newS = new int[S.length - 1];
        
        for (int i = 0; i < S.length; i ++){
            if (S[i] > max){
                max = S[i];
                index = i;
            }
        }
        
        int j = 0;
        
        for (j = 0; j < index; j++){
            newS[j] = S[j];
        }
        
        for (int m = index + 1; m < S.length; m ++){
            newS[j] = S[m];
            j++;
        }
        // get the result for the new array
        ArrayList<ArrayList<Integer>> pre_res = subsets(newS);
        res.addAll(pre_res);
        
        for ( ArrayList<Integer> p: pre_res){
            ArrayList<Integer> new_item = new ArrayList<Integer>();
            new_item.addAll(p);
            new_item.add(max);
            res.add(new_item);
        }
        
        return res;
    }
}