Showing posts with label Facebook. Show all posts
Showing posts with label Facebook. Show all posts

Sunday, September 2, 2018

437. Path Sum III

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11


Solution:

We can recursively check:

1. can we get a path sum to target from current node?
2. can we get a path sum to target from the child of this node?


Code:


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int pathSum(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        return helper(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }
    
    public int helper(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        return (sum == root.val ? 1 : 0) + helper(root.left, sum - root.val) + helper(root.right, sum - root.val);
    }
}

Tuesday, August 8, 2017

653. Two Sum IV - Input is a BST

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.
Example 1:
Input: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 9

Output: True
Example 2:
Input: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 28

Output: False


Solution:

The inorder sequence of BST is sorted.

So firstly we use O(n) time to construct a sorted ArrayList.

After that, we can apply two pointers from the start and end of the ArrayList to search for a target sum.

The time complexity of the search is also (n).

Thus, the time complexity is O(n) and the space complexity is O(n).


Code:


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean findTarget(TreeNode root, int k) {
        List<Integer> list = new ArrayList<>();
        inorder(root, list);
        int i = 0;
        int j = list.size() - 1;
        while (i < j) {
            int sum = list.get(i) + list.get(j);
            if (sum == k) {
                return true;
            }
            else if (sum < k) {
                i++;
            }
            else {
                j--;
            }
        }
        return false;
    }

    public List<Integer> inorder(TreeNode root, List<Integer> list) {
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            list.add(root.val);
            root = root.right;
        }
        return list;
    }
}

Wednesday, June 21, 2017

410. Split Array Largest Sum

Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.
Note:
If n is the length of array, assume the following constraints are satisfied:
  • 1 ≤ n ≤ 1000
  • 1 ≤ m ≤ min(50, n)
Examples: 
Input:
nums = [7,2,5,10,8]
m = 2

Output:
18

Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.



Solution:

Assume that we have already split the array which satisfy the condition.

Let's say sub array sub is the one have the maximum sum of all sub arrays.

We know the sum of this array bound satisfies:

1. bound >= the largest element of the array.

2. bound <= the sum of the array.

Therefore, we can use binary search to find the first occurrence of bound that in the above range that can be splitter into m partitions.

The time complexity is O(nlogn) and the space complexity is O(1).



Code:


public class Solution {
    public int splitArray(int[] nums, int m) {
        int start = 0;
        int end = 0;
        for (int num : nums) {
            start = Math.max(start, num);
            end += num;
        }
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (isValid(nums, mid, m)) {
                end = mid;
            }
            else {
                start = mid;
            }
        }
        return isValid(nums, start, m) ? start : isValid(nums, end, m) ? end : -1;
    }
    
    public boolean isValid(int[] nums, int bound, int m) {
        int count = 1;
        int sum = 0;
        for (int num : nums) {
            sum += num;
            if (sum > bound) {
                count++;
                sum = num;
                if (count > m) {
                    return false;
                }
            }
        }
        return true;
    }
}

Tuesday, June 13, 2017

25. Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For example,
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5



Solution:

For example if the linked list is 1 - > 2 -> 3 -> 4 and k = 2.

In order to flip, we need to have 1's previous node.

Therefore we use a dummy node as the head.

d -> 1 - > 2 -> 3 -> 4

The flip is the classic reverse linked list method.

We use a for loop to reverse each pair k times.

After flipping, we connect 1 to 3 and make 1 the new head.

d -> 2 -> 1 -> 3 -> 4

For each flip, we first check if there exists k nodes. If not, we simply return null.



Code:


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        head = dummy;
        while (head != null) {
            head = reverseK(head, k);
        }
        return dummy.next;
    }
    
    public ListNode reverseK(ListNode head, int k) {
        ListNode curr = head.next;
        for (int i = 0; i < k; i++) {
            if (curr == null) {
                return null;
            }
            curr = curr.next;
        }
        
        ListNode prev = null;
        curr = head.next;
        for (int i = 0; i < k; i++) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        ListNode newHead = head.next;
        newHead.next = curr;
        head.next = prev;
        return newHead;
    }
}

Wednesday, June 7, 2017

275. H-Index II

Follow up for H-Index: What if the citations array is sorted in ascending order? Could you optimize your algorithm?



Solution:

The idea is to use binary search to find the first occurrence satisfy:

citations[index] >= citations.length - index.

This condition means there are citations[index] papers have at least citations[index] citations.

The time complexity is O(logn) and the space complexity is O(n).



Code:


public class Solution {
    public int hIndex(int[] citations) {
        if (citations == null || citations.length == 0) {
            return 0;
        }
        // find first occurance that citations[index] >= citations.length - index
        int n = citations.length;
        int start = 0;
        int end = n - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (citations[mid] >= n - mid) {
                end = mid;
            }
            else {
                start = mid;
            }
        }
        if (citations[start] >= n - start) {
            return n - start;
        }
        if (citations[end] >= n - end) {
            return n - end;
        }
        return 0;
    }
}

Tuesday, June 6, 2017

494. Target Sum

You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.
Find out how many ways to assign symbols to make sum of integers equal to target S. 
Example 1:
Input: nums is [1, 1, 1, 1, 1], S is 3. 
Output: 5
Explanation: 

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

There are 5 ways to assign symbols to make the sum of nums be target 3.
Note:
  1. The length of the given array is positive and will not exceed 20. 
  2. The sum of elements in the given array will not exceed 1000.
  3. Your output answer is guaranteed to be fitted in a 32-bit integer.



Solution:

Method 1: DFS

This problem is a simplified version of Expression Add Operators. 

We only need to consider + and -.

We go through each number and try + or -. When we reach the end of the input, we check if the sum equals to the target.

If so, we increment the result.

The time complexity is O(2n), since we have two choices at each position.



Code:


public class Solution {
    private int result = 0;
    public int findTargetSumWays(int[] nums, int S) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        helper(nums, S, 0, 0);
        return result;
    }
    public void helper(int[] nums, int target, int sum, int pos) {
        if (pos == nums.length) {
            if (sum == target) {
                result++;
            }
            return;
        }
        helper(nums, target, sum + nums[pos], pos + 1);
        helper(nums, target, sum - nums[pos], pos + 1);
    }
}



Method 2: Dynamic Programming

The idea is to split the numbers into two partitions: nums with '+' and nums with '-'.

We want find such partition that

sum(P) - sum(N) == target

sum(P) - sum(N) + sum(All) == target + sum(All)

sum(P) - sum(N) + sum(P) + sum(N) == target + sum(All)

sum(P) == (target + sum(All)) / 2

We know sum(P) is still integer. So if target + sum(All) is odd number, there is no such partition.

Otherwise, the problem becomes Partition Equal Subset Sum.

The time complexity is O(n2) and the space complexity is O(n).



Code:


public class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum < S || (S + sum) % 2 != 0) {
            return 0;
        }
        return findWays(nums, (S + sum) / 2);
    }
    
    public int findWays(int[] nums, int target) {
        int[] ways = new int[target + 1];
        ways[0] = 1;
        for (int num : nums) {
            for (int i = target; i >= num; i--) {
                ways[i] += ways[i - num];
            }
        }
        return ways[target];
    }
}

68. Text Justification

Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly L characters.
Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be left justified and no extra space is inserted between words.
For example,
words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16.
Return the formatted lines as:
[
   "This    is    an",
   "example  of text",
   "justification.  "
]
Note: Each word is guaranteed not to exceed L in length.
Corner Cases:
  • A line other than the last line might contain only one word. What should you do in this case?
    In this case, that line should be left-justified.



Solution:

We keep a last variable to store the first index we can use in a line.

We use count to store the total length of words (no space).

If count plus one more word and spaces exceed maxWidth, we know we have to use this count.

To evenly distributed spaces, we use (maxWidth - count) / (number of words in this line) as space between two words. The extra space is (maxWidth - count) % (number of words in this line).

We also need to consider when a word is the last in this line, we do not have spaces after it.

A corner case is to deal with the last line, where we fill spaces after the last word.

A annotated and clear version of code can be found HERE.



Code:


public class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> result = new ArrayList<>();
        if (words == null || words.length == 0) {
            return result;
        }
        int last = 0;
        int count = 0;
        for (int i = 0; i < words.length; i++) {
            // words[i] cannot fit this line.
            // We can only put from words[last] to words[i - 1].
            if (count + words[i].length() + (i - last) > maxWidth) {
                int space = 0;
                int extra = 0;
                // We have i - last words in this line.
                // So we have i - last - 1 intervals.
                if (i - last - 1 > 0) {
                    space = (maxWidth - count) / (i - last - 1);
                    extra = (maxWidth - count) % (i - last - 1);
                }
                StringBuilder sb = new StringBuilder();
                for (int j = last; j < i; j++) {
                    sb.append(words[j]);
                    // There is no space after the last word in this line.
                    if (j == i - 1) {
                        break;
                    }
                    for (int k = 0; k < space; k++) {
                        sb.append(" ");
                    }
                    if (extra > 0) {
                        sb.append(" ");
                        extra--;
                    }
                }
                // If this line has not filled, fill trailing spaces.
                while (sb.length() < maxWidth) {
                    sb.append(" ");
                }
                result.add(sb.toString());
                count = 0;
                last = i;
            }
            count += words[i].length();
        }
        // To deal with the last line
        StringBuilder sb = new StringBuilder();
        for (int i = last; i < words.length; i++) {
            sb.append(words[i]);
            if (sb.length() < maxWidth) {
                sb.append(" ");
            }
        }
        while (sb.length() < maxWidth) {
            sb.append(" ");
        }
        result.add(sb.toString());
        return result;
    }
}

218. The Skyline Problem

A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skylineformed by these buildings collectively (Figure B).
BuildingsSkyline Contour
The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.
For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .
The output is a list of "key points" (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.
For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].
Notes:
  • The number of buildings in any input list is guaranteed to be in the range [0, 10000].
  • The input list is already sorted in ascending order by the left x position Li. 
  • The output list must be sorted by the x position. 
  • There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...[2 3], [4 5], [7 5], [11 5], [12 7]...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...[2 3], [4 5], [12 7], ...]



Solution:

1. Create height coordinates. We use negative value to denote a start point, and positive value to denote an end point.

2. Sort the heights. 3 corner cases: same start, same end, and end == start.

3. Create a max heap with initial value 0.

4. Go through the heights.

a). If it is a start point, put it into the heap. If the top of heap changes, this point with the new heap value (itself) should be in the final result.

b). If it is an end point,  remove it from the heap. If the top of heap changes, this point with the new heap top value should be in the final result.

Detailed explanation check out this Youtube Video.

TreeMap support O(logn) on insert and remove operation.

The time complexity is O(nlogn) and the space complexity is O(n).



Code:


public class Solution {
    public List<int[]> getSkyline(int[][] buildings) {
        List<int[]> heights = new ArrayList<>();
        for (int[] building : buildings) {
            heights.add(new int[] {building[0], -building[2]});
            heights.add(new int[] {building[1], building[2]});
        }
        Collections.sort(heights, new Comparator<int[]>() {
            public int compare(int[] x, int[] y) {
                if (x[0] == y[0]) {
                    return x[1] - y[1];
                }
                return x[0] - y[0];
            }
        });
        List<int[]> result = new ArrayList<>();
        TreeMap<Integer, Integer> map = new TreeMap<>(Collections.reverseOrder());
        map.put(0, 1);
        int prevHeight = 0;
        for (int[] height : heights) {
            if (height[1] < 0) {
                Integer count = map.get(-height[1]);
                count = count == null ? 1 : count + 1;
                // Use a count to store the frequency of this height.
                // The reason is that map cannot store duplicate items.
                map.put(-height[1], count);
            }
            else {
                Integer count = map.get(height[1]);
                if (count == 1) {
                    map.remove(height[1]);
                }
                else {
                    map.put(height[1], count - 1);
                }
            }
            int currHeight = map.firstKey();
            if (currHeight != prevHeight) {
                result.add(new int[] {height[0], currHeight});
                prevHeight = currHeight;
            }
        }
        return result;
    }
}




public class Solution {
    public List<int[]> getSkyline(int[][] buildings) {
        List<int[]> result = new ArrayList<>();
        List<int[]> heights = new ArrayList<>();
        for (int[] building : buildings) {
            heights.add(new int[] {building[0], -building[2]});
            heights.add(new int[] {building[1], building[2]});
        }
        Collections.sort(heights, new Comparator<int[]>() {
            public int compare(int[] x, int[] y) {
                if(x[0] == y[0]) {
                    return x[1] - y[1];
                }
                return x[0] - y[0];
            }    
        });
        Queue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.offer(0);
        int prev = 0;
        for (int[] height : heights) {
            if (height[1] < 0) {
                maxHeap.offer(-height[1]);
            }
            else {
                maxHeap.remove(height[1]);
            }
            int curr = maxHeap.peek();
            if (curr != prev) {
                result.add(new int[] {height[0], curr});
                prev = curr;
            }
        }
        return result;
    }
}

Monday, June 5, 2017

85. Maximal Rectangle

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
For example, given the following matrix:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 6.



Solution:

This problem can be split to the sub problems:

1. calculate the largest rectangle histogram of row 1.

2. calculate the largest rectangle histogram of row 1 and row 2 together.

3. calculate the largest rectangle histogram of row 1, 2, and 3 together.

...


n. calculate the largest rectangle histogram of row 1, 2, to n together.

Take the max of the above largest rectangle histograms.

We know Largest Rectangle in Histogram can be done with O(n) time and O(n) space.

Therefore, this problem can be done in O(mn) time with O(n) space.



Code:


public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        if (matrix[0] == null || matrix[0].length == 0) {
            return 0;
        }
        int[] heights = new int[matrix[0].length];
        int max = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                heights[j] = i == 0 ? matrix[i][j] - '0' : matrix[i][j] == '1' ? heights[j] + 1 : 0;
            }
            max = Math.max(max, findMaxHistogram(heights));
        }
        return max;
    }
    
    public int findMaxHistogram(int[] heights) {
        int max = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i <= heights.length; i++) {
            int curr = i == heights.length ? -1 : heights[i];
            while (!stack.isEmpty() && curr <= heights[stack.peek()]) {
                int height = heights[stack.pop()];
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                max = Math.max(max, height * width);
            }
            stack.push(i);
        }
        return max;
    }
}

10. Regular Expression Matching

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



Solution:

Method 1: DP

We use dynamic programming to determine whether s and p are match.

boolean match[i][j]: whether the first i characters in s match the first j characters in p.

There are two cases to consider:

1. s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j) == '.'.

match[i - 1][j - 1]

2. p.charAt(j) == '*'
 
a). match[i][j - 2], 0 occurrence of p.charAt(j - 1)
      or
b). match[i - 1][j], if s.charAt(i) == p.charAt(j - 1) || p.charAt(j - 1) == '.'.

The time complexity is O(mn) and the space complexity is O(mn) as well.



Code:


public class Solution {
    public boolean isMatch(String s, String p) {
        boolean[][] match = new boolean[s.length() + 1][p.length() + 1];
        match[0][0] = true;
        
        // deal with a*, a*b*, a*b*c*...
        for (int i = 1; i < match[0].length; i++) {
            if (p.charAt(i - 1) == '*') {
                match[0][i] = match[0][i - 2];
            }
        }
        for (int i = 1; i < match.length; i++) {
            for (int j = 1; j < match[0].length; j++) {
                if (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1)) {
                    match[i][j] = match[i - 1][j - 1];
                }
                else if (p.charAt(j - 1) == '*') {
                    
                    // s: x   p xa*, we check a* is empty, which is match[i][j - 2];
                    match[i][j] = match[i][j - 2];
                    
                    // s: xa  p: xa* -> a is part of a*, so we check s: x  p: xa*, which is match[i - 1][j]
                    if (p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1)) {
                        match[i][j] = match[i][j] || match[i - 1][j];
                    }
                }
                else {
                    match[i][j] = false;
                }
            }
        }
        return match[s.length()][p.length()];
    }
}



Method 2: Optimization (Rolling Array)

We need to update match[i % 2][0] in the j loop.



Code:


public class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] match = new boolean[2][n + 1];
        match[0][0] = true;
        
        // p: a*, a*b*, a*b*c*...
        for (int j = 1; j <= n; j++) {
            if (p.charAt(j - 1) == '*') {
                match[0][j] = match[0][j - 2];
            }
        }
        
        for (int i = 1; i <= m; i++) {
            match[i % 2][0] = false;
            for (int j = 1; j <= n; j++) {
                if (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1)) {
                    match[i % 2][j] = match[(i - 1) % 2][j - 1];
                }
                else if (p.charAt(j - 1) == '*') {
                    // s: x  p: xa*
                    match[i % 2][j] = match[i % 2][j - 2];
                    
                    // s: xa  p: xa*  p: x.*
                    if (p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1)) {
                        match[i % 2][j] = match[i % 2][j] || match[(i - 1) % 2][j];
                    }
                }
                else {
                    match[i % 2][j] = false;
                }
                
            }
        }
        
        return match[m % 2][n];
    }
}

Sunday, June 4, 2017

78. Subsets

Given a set of distinct integers, nums, return all possible subsets.
Note: The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,3], a solution is:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]



Solution:

Method 1: DFS

Use DFS to traverse all possible combinations and store all of them into results.

To keep the subsets in order, we first sort the input array.



Code:


public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return result;
        }
        helper(nums, result, new ArrayList<Integer>(), 0);
        return result;
    }
    
    public void helper(int[] nums, List<List<Integer>> result, List<Integer> list, int pos) {
        result.add(new ArrayList<Integer>(list));
        
        for (int i = pos; i < nums.length; i++) {
            list.add(nums[i]);
            helper(nums, result, list, i + 1);
            list.remove(list.size() - 1);
        }
    }
}



Method 2: Bitset