Combinations Solutions in Java

/// Source : https://leetcode.com/problems/combinations/description/
/// Author : liuyubobobo
/// Time   : 2017-11-18

import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;

/// Naive Recursive
/// Time Complexity: O(n^k)
/// Space Complexity: O(k)
public class Solution1 {

    private ArrayList<List<Integer>> res;

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

        res = new ArrayList<List<Integer>>();
        if(n <= 0 || k <= 0 || k > n)
            return res;

        LinkedList<Integer> c = new LinkedList<Integer>();
        generateCombinations(n, k, 1, c);

        return res;
    }

    private void generateCombinations(int n, int k, int start, LinkedList<Integer> c){

        if(c.size() == k){
            res.add((List<Integer>)c.clone());
            return;
        }

        for(int i = start ; i <= n ; i ++){
            c.addLast(i);
            generateCombinations(n, k, i + 1, c);
            c.removeLast();
        }

        return;
    }

    private static void printList(List<Integer> list){
        for(Integer e: list)
            System.out.print(e + " ");
        System.out.println();
    }

    public static void main(String[] args) {

        List<List<Integer>> res = (new Solution1()).combine(4, 2);
        for(List<Integer> list: res)
            printList(list);
    }
}

/// Source : https://leetcode.com/problems/combinations/description/
/// Author : liuyubobobo
/// Time   : 2017-11-18

import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;


/// Naive Recursive Optimized
/// Time Complexity: O(n^k)
/// Space Complexity: O(k)
public class Solution2 {

    private ArrayList<List<Integer>> res;

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

        res = new ArrayList<List<Integer>>();
        if(n <= 0 || k <= 0 || k > n)
            return res;

        LinkedList<Integer> c = new LinkedList<Integer>();
        generateCombinations(n, k, 1, c);

        return res;
    }

    private void generateCombinations(int n, int k, int start, LinkedList<Integer> c){

        if(c.size() == k){
            res.add((List<Integer>)c.clone());
            return;
        }

        // i will at most be n - (k - c.size()) + 1
        for(int i = start ; i <= n - (k - c.size()) + 1 ; i ++){
            c.addLast(i);
            generateCombinations(n, k, i + 1, c);
            c.removeLast();
        }

        return;
    }

    private static void printList(List<Integer> list){
        for(Integer e: list)
            System.out.print(e + " ");
        System.out.println();
    }

    public static void main(String[] args) {

        List<List<Integer>> res = (new Solution2()).combine(4, 2);
        for(List<Integer> list: res)
            printList(list);
    }
}

/// Source : https://leetcode.com/problems/combinations/description/
/// Author : liuyubobobo
/// Time   : 2019-04-08

import java.util.List;
import java.util.ArrayList;


/// Using bit mask
/// Time Complexity: O(2^n * n)
/// Space Complexity: O(1)
public class Solution3 {

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

        List<List<Integer>> res = new ArrayList<>();

        int LIMIT = (1 << n);
        for(int i = 0; i < LIMIT; i ++){
            List lst = getCombination(i);
            if(lst.size() == k) res.add(lst);
        }
        return res;
    }

    private List getCombination(int num){

        ArrayList<Integer> res = new ArrayList<>();
        int i = 1;
        while (num != 0){
            if(num % 2 == 1) res.add(i);
            i ++;
            num /= 2;
        }
        return res;
    }
}

/// Source : https://leetcode.com/problems/combinations/description/
/// Author : liuyubobobo
/// Time   : 2019-04-08

import java.util.List;
import java.util.ArrayList;


/// Get all the combinations in place
/// Find the first non-saturated element and increase it
///
/// Time Complexity: O(k * C(n, k))
/// Space Complexity: O(1)
public class Solution4 {

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

        List<List<Integer>> res = new ArrayList<>();

        int[] c = new int[k];
        for(int i = 1; i <= k; i ++)
            c[i - 1] = i;
        res.add(getList(c));

        while(c[0] != n - k + 1){

            if(c[k - 1] != n) c[k - 1] ++;
            else{
                for(int i = k - 1; i >= 0; i --)
                    if(c[i] != i + n - k + 1){
                        c[i] ++;
                        for(int j = i + 1; j < k; j ++)
                            c[j] = c[j - 1] + 1;
                        break;
                    }
            }
            res.add(getList(c));
        }
        return res;
    }

    private List getList(int[] arr){
        ArrayList<Integer> res = new ArrayList<>();
        for(int e: arr)
            res.add(e);
        return res;
    }
}

/// Source : https://leetcode.com/problems/combinations/description/
/// Author : liuyubobobo
/// Time   : 2019-04-08

import java.util.List;
import java.util.ArrayList;


/// Get all the combinations in place
/// find the first j which nums[j] + 1 != nums[j + 1] and increase nums[j]
/// See here for details: https://leetcode.com/problems/combinations/solution/
///
/// Time Complexity: O(k * C(n, k))
/// Space Complexity: O(1)
public class Solution5 {

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

        List<List<Integer>> res = new ArrayList<>();

        int[] c = new int[k + 1];
        for(int i = 1; i <= k; i ++)
            c[i - 1] = i;
        c[k] = n + 1;

        int j = 0;
        while(j < k){
            res.add(getList(c));

            for(j = 0; j < k && c[j] + 1 == c[j + 1]; j ++)
                c[j] = j + 1;
            c[j] ++;
        }
        return res;
    }

    private List getList(int[] arr){
        ArrayList<Integer> res = new ArrayList<>();
        for(int i = 0; i < arr.length - 1; i ++)
            res.add(arr[i]);
        return res;
    }
}