LeetCode 77 - Combinations


Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
For example,
If n = 4 and k = 2, a solution is:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]
 For choosing number in a specific layer, we can use a iteration, e.g. in the first layer, we try 1-5.  While for step in another layer, we can use recursive call.  Parameters we need for a recursive call are the current combination, the combination result set, the n, the k, and the start point of iteration (e.g. if we chose 1 for the first position, start point of 2nd position is 2; while if we chose 2 for the first position, start point of second position is 3).  
X. DFS
Code from http://blog.csdn.net/u010500263/article/details/18435495



From this example, we can see that in the first position of the resulting combinations we can chose number 1-5.  Assume that we chose 1 for the 1 position of the combination, then we can choose 2-5 for the second position.  Till we chosen numbers for all position, we can have one possible combination.



However, when we chose 3 for the first position and 5 for the second position, we don't have any other number to choose for the 3rd position. (former number must be smaller than the following number).







Now we have the rules of this problem, and we can try to implement these rules.  For choosing number in a specific layer, we can use a iteration, e.g. in the first layer, we try 1-5.  While for step in another layer, we can use recursive call.  Parameters we need for a recursive call are the current combination, the combination result set, the n, the k, and the start point of iteration (e.g. if we chose 1 for the first position, start point of 2nd position is 2; while if we chose 2 for the first position, start point of second position is 3).  





public ArrayList<ArrayList<Integer>> combine(int n, int k) {




ArrayList<ArrayList<Integer>> combSet = new ArrayList<ArrayList<Integer>>();




ArrayList<Integer> comb = new ArrayList<Integer>();




if(n<k) return combSet;




helper(n, k, combSet, comb, 1);




return combSet;




}




public void helper(int n, int k, ArrayList<ArrayList<Integer>> combSet, ArrayList<Integer> comb, int start){




// one possible combinition constructured




if(comb.size() == k){




combSet.add(new ArrayList<Integer> (comb));




return;




}




else{




for(int i=start; i<=n; i++){// try each possibility number in current position




comb.add(i);




helper(n, k, combSet, comb, i+1); // after selecting number for current position, process next position




comb.remove(comb.size()-1); // clear the current position to try next possible number




}




}




}
Code from http://www.darrensunny.me/leetcode-combinations/
http://blog.csdn.net/linhuanmars/article/details/21260217
https://jiajiewu.wordpress.com/2014/08/19/leetcode-combinations/
Good naming -> subResult
    public ArrayList<ArrayList<Integer>> combine(int n, int k) {
        if (n<=0||k<=0){
            return null;
        }
         
        ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
         
        int st=1;
        int num=0;
        ArrayList<Integer> subResult=new ArrayList<Integer>();
        buildResult(st, num, k, n, subResult, result);
         
        return result;
    }
     
    private void buildResult(int start, int currentNum, int k, int n, ArrayList<Integer> subResult, ArrayList<ArrayList<Integer>> result)
    {
        if (currentNum==k){
            ArrayList<Integer> temp=new ArrayList<Integer>(subResult);
            result.add(temp);
            return;
        }
         
        for (int i=start; i<=n; i++){
            subResult.add(i);
            buildResult(i+1, currentNum+1, k, n, subResult, result);
            subResult.remove(subResult.size()-1);
        }
    }
http://www.programcreek.com/2014/03/leetcode-combinations-java/
Use List as stack - Stack class is deprecated in java.
public ArrayList<ArrayList<Integer>> combine(int n, int k) {
 ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
 
 if (n <= 0 || n < k)
  return result;
 
 ArrayList<Integer> item = new ArrayList<Integer>();
 dfs(n, k, 1, item, result); // because it need to begin from 1
 
 return result;
}
 
private void dfs(int n, int k, int start, ArrayList<Integer> item,
  ArrayList<ArrayList<Integer>> res) {
 if (item.size() == k) {
  res.add(new ArrayList<Integer>(item));
  return;
 }
 
 for (int i = start; i <= n; i++) {
  item.add(i);
  dfs(n, k, i + 1, item, res);
  item.remove(item.size() - 1);
 }
}

public List<List<Integer>> combine(int n, int k) { List<List<Integer>> ans = new LinkedList<List<Integer>>(); combineHelper(ans, new LinkedList<Integer>(), n, k, 1); return ans; } private void combineHelper(List<List<Integer>> ans, List<Integer> current, int n, int k, int start) { if (current.size() == k) { ans.add(current); return; } for (int i = start; i <= n; i++) { List<Integer> newCurrent = new LinkedList<Integer>(current);// newCurrent.add(i);//\\ combineHelper(ans, newCurrent, n, k, i + 1); } }

X. Use int[]
[leetcode] Combinations | 给数字n和k，求所有由1～n组成的长度为k的combination
这个题和上两道相比简单了不少，因为是固定长度所以不用stack了，用int[]加一个position variable。每次在这个pos上一个一个试数，每确定一个就在下一个pos处recurse。
public ArrayList<ArrayList<Integer>> combine(int n, int k) {
  ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
  if (k <= 0 || n < 1)
    return result;
  populateResult(1, n, 0, result, new int[k]);
  return result;
}
private void populateResult(int startNum, int endNum, int pos, 
            ArrayList<ArrayList<Integer>> result, int[] path) {
  if (pos == path.length) {
    ArrayList<Integer> combination = new ArrayList<Integer>();
    convertArrayToList(path, combination);
    result.add(combination);
    return;
  }
  for (int i = startNum; i <= endNum; i++) { //i is using which number
    path[pos] = i;
    populateResult(i + 1, endNum, pos + 1, result, path); //use next 
                                            //number on next position
    //as i++, use next number on same position
  }
}

X.
Basically, this solution follows the idea of the mathematical formula C(n,k)=C(n-1,k-1)+C(n-1,k).
Here C(n,k) is divided into two situations. Situation one, number n is selected, so we only need to select k-1 from n-1 next. Situation two, number n is not selected, and the rest job is selecting k from n-1.
public List<List<Integer>> combine(int n, int k) { if (k == n || k == 0) { List<Integer> row = new LinkedList<>(); for (int i = 1; i <= k; ++i) { row.add(i); } return new LinkedList<>(Arrays.asList(row));//? why not new LinkedList<>(row) } List<List<Integer>> result = this.combine(n - 1, k - 1); result.forEach(e -> e.add(n)); result.addAll(this.combine(n - 1, k)); return result; }
public List<List<Integer>> combine(int n, int k) { List<List<Integer>> result = new ArrayList<List<Integer>>(); if (k > n || k < 0) { return result; } if (k == 0) { result.add(new ArrayList<Integer>()); return result; } result = combine(n - 1, k - 1); for (List<Integer> list : result) { list.add(n); } result.addAll(combine(n - 1, k)); return result; }
public List<List<Integer>> combine(int n, int k) { return combine(n,1,k); } public List<List<Integer>> combine(int n,int current,int k){ List<List<Integer>> result = new LinkedList<List<Integer>>(); if(k==0) { result.add(new LinkedList<Integer>()); return result; } if(current>n) return result; for(List<Integer> res:combine(n,current+1,k)){ result.add(res); } for(List<Integer> res:combine(n,current+1,k-1)){ res.add(0,current); result.add(res); } return result; }

X. Iterative Version
https://leetcode.com/discuss/24600/iterative-java-solution
The idea is to iteratively generate combinations for all lengths from 1 to k. We start with a list of all numbers <= n as combinations for k == 1. When we have all combinations of length k-1, we can get the new ones for a length k with trying to add to each one all elements that are <= n and greater than the last element of a current combination.
public List<List<Integer>> combine(int n, int k) { if (k == 0 || n == 0 || k > n) return Collections.emptyList(); List<List<Integer>> combs = new ArrayList<>(); for (int i = 1; i <= n; i++) combs.add(Arrays.asList(i)); for (int i = 2; i <= k; i++) { List<List<Integer>> newCombs = new ArrayList<>(); for (int j = i; j <= n; j++) { for (List<Integer> comb : combs) { if (comb.get(comb.size()-1) < j) { List<Integer> newComb = new ArrayList<>(comb); newComb.add(j); newCombs.add(newComb); } } } combs = newCombs; } return combs; }
TODO: 
http://www.sigmainfy.com/blog/leetcode-combinations.html
https://leetcode.com/discuss/67405/java-my-iterative-13ms-and-recursive-7ms-solutions
public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> list = new ArrayList<List<Integer>>();
    List<Integer> kind = new ArrayList<Integer>();
    int i = 1;
    while(i<=n || kind.size()!=0){
        if(kind.size()==k){
            list.add(new ArrayList(kind));
        }
        if(i>n||kind.size()==k){
            i = kind.get(kind.size()-1)+1;
            kind.remove(kind.size()-1);
        }
        else{
            kind.add(i);
            i++;
        }
    }
    return list;
}
https://leetcode.com/discuss/14645/iterative-version

from http://gongxuns.blogspot.com/2012/12/leetcodecombinations.html
Use iterations to generate different levels of solutions. The first level solution is the set of all first numbers in the final solution is {1,2,...,n-k+1}. To avoid duplicates, for the next level, always add a larger number to the element in current level.
public ArrayList<ArrayList<Integer>> combine(int n, int k) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if(k==0) return res;
        res.add(new ArrayList<Integer>());
        for(int i=0;i<k;i++){
             ArrayList<ArrayList<Integer>> prev = new ArrayList<ArrayList<Integer>>();
             for(ArrayList<Integer> temp:res){
                int a=0;
                if(temp.size()>0)
                    a=temp.get(temp.size()-1);
                for(int j=a+1;j<=n-k+1+i;j++){
                    ArrayList<Integer> b= new ArrayList<Integer>(temp);
                    b.add(j);
                    prev.add(b);
                }
             }
            res = new ArrayList<ArrayList<Integer>>(prev);
        }
        return res;
    }
https://leetcode.com/discuss/37021/1-liner-3-liner-4-liner
http://www.geeksforgeeks.org/print-all-possible-combinations-of-r-elements-in-a-given-array-of-size-n/
Method 1 (Fix Elements and Recur)
We create a temporary array ‘data[]‘ which stores all outputs one by one. The idea is to start from first index (index = 0) in data[], one by one fix elements at this index and recur for remaining indexes. Let the input array be {1, 2, 3, 4, 5} and r be 3. We first fix 1 at index 0 in data[], then recur for remaining indexes, then we fix 2 at index 0 and recur. Finally, we fix 3 and recur for remaining indexes. When number of elements in data[] becomes equal to r (size of a combination), we print data[].
void printCombination(int arr[], int n, int r)
{
    // A temporary array to store all combination one by one
    int data[r];
    // Print all combination using temprary array 'data[]'
    combinationUtil(arr, data, 0, n-1, 0, r);
}
/* arr[]  ---> Input Array
   data[] ---> Temporary array to store current combination
   start & end ---> Staring and Ending indexes in arr[]
   index  ---> Current index in data[]
   r ---> Size of a combination to be printed */
void combinationUtil(int arr[], int data[], int start, int end, int index, int r)
{
    // Current combination is ready to be printed, print it
    if (index == r)
    {
        for (int j=0; j<r; j++)
            printf("%d ", data[j]);
        printf("\n");
        return;
    }
    // replace index with all possible elements. The condition
    // "end-i+1 >= r-index" makes sure that including one element
    // at index will make a combination with remaining elements
    // at remaining positions
    for (int i=start; i<=end && end-i+1 >= r-index; i++)
    {
        data[index] = arr[i];
        combinationUtil(arr, data, i+1, end, index+1, r);
    }
}
How to handle duplicates?
Note that the above method doesn’t handle duplicates. For example, if input array is {1, 2, 1} and r is 2, then the program prints {1, 2} and {2, 1} as two different combinations. We can avoid duplicates by adding following two additional things to above code.
1) Add code to sort the array before calling combinationUtil() in printCombination()
2) Add following lines at the end of for loop in combinationUtil()
        // Since the elements are sorted, all occurrences of an element
        // must be together
        while (arr[i] == arr[i+1])
             i++;
See this for an implementation that handles duplicates.
Method 2 (Include and Exclude every element)
1) The element is included in current combination (We put the element in data[] and increment next available index in data[])
2) The element is excluded in current combination (We do not put the element and do not change index)
This method is mainly based on Pascal’s Identity, i.e. ncr = n-1cr + n-1cr-1
oid printCombination(int arr[], int n, int r)
{
    // A temporary array to store all combination one by one
    int data[r];
    // Print all combination using temprary array 'data[]'
    combinationUtil(arr, n, r, 0, data, 0);
}
/* arr[]  ---> Input Array
   n      ---> Size of input array
   r      ---> Size of a combination to be printed
   index  ---> Current index in data[]
   data[] ---> Temporary array to store current combination
   i      ---> index of current element in arr[]     */
void combinationUtil(int arr[], int n, int r, int index, int data[], int i)
{
    // Current cobination is ready, print it
    if (index == r)
    {
        for (int j=0; j<r; j++)
            printf("%d ",data[j]);
        printf("\n");
        return;
    } 
    // When no more elements are there to put in data[]
    if (i >= n)
        return; 
    // current is included, put next at next location
    data[index] = arr[i];
    combinationUtil(arr, n, r, index+1, data, i+1); 
    // current is excluded, replace it with next (Note that
    // i+1 is passed, but index is not changed)
    combinationUtil(arr, n, r, index, data, i+1);
}
Read full article from [leet code] Combinations - 伪技回忆录 - 博客频道 - CSDN.NET
at
Labels: , , , , , , , , , , ,

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts