77, Combinations

I Problem

Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].

You may return the answer in any order.

Example 1
Input: n = 4, k = 2
Output: [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1, 2] and [2, 1] are considered to be the same combination.

Example 2
Input: n = 1, k = 1
Output: [[1]]
Explanation: There is 1 choose 1 = 1 total combination.

Constraints

• 1 <= n <= 20
• 1 <= k <= n

Related Topics

• Backtracking

II Solution

Approach 1: Backtracking

pub fn combine(n: i32, k: i32) -> Vec<Vec<i32>> {
    const BACKTRACKING: fn(i32, i32, usize, &mut Vec<i32>, &mut Vec<Vec<i32>>) =
        |start, n, k, path, res| {
            // prune
            if (n - start + 1) as usize + path.len() < k {
                return;
            }

            if path.len() == k {
                res.push(path.clone());
                return;
            }

            for i in start..=n {
                path.push(i);
                BACKTRACKING(i + 1, n, k, path, res);
                path.pop();
            }
        };

    let mut res = vec![];

    BACKTRACKING(1, n, k as usize, &mut vec![], &mut res);

    res
}

@FunctionalInterface
interface QuintConsumer<A, B, C, D, E> {
    void accept(A a, B b, C c, D d, E e);
}

QuintConsumer<Integer, Integer, Integer, List<Integer>, List<List<Integer>>> recur = 
    (start, n, k, path, res) -> {
        // prune
        if (n - start + 1 + path.size() < k) {
            return;
        }
    
        if (path.size() == k) {
            res.add(new ArrayList<>(path));
            return;
        }
    
        for (int i = start; i <= n; i++) {
            path.add(i);
            this.recur.accept(i + 1, n, k, path, res);
            path.removeLast();
        }
    };

public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> res = new ArrayList<>();

    this.recur.accept(1, n, k, new ArrayList<>(), res);

    return res;
}

Approach 2: Combination Enum(Recursion Impl)

pub fn combine(n: i32, k: i32) -> Vec<Vec<i32>> {
    const DFS: fn(i32, i32, usize, &mut Vec<i32>, &mut Vec<Vec<i32>>) =
        |start, n, k, path, res| {
            // prune
            if (n - start + 1) as usize + path.len() < k {
                return;
            }

            if path.len() == k {
                res.push(path.clone());
                return;
            }

            path.push(start);
            DFS(start + 1, n, k, path, res);
            path.pop();
            DFS(start + 1, n, k, path, res);
        };

    let mut res = vec![];

    DFS(1, n, k as usize, &mut vec![], &mut res);

    res
}

QuintConsumer<Integer, Integer, Integer, List<Integer>, List<List<Integer>>> dfs = 
    (start, n, k, path, res) -> {
        // prune
        if (n - start + 1 + path.size() < k) {
            return;
        }
    
        if (path.size() == k) {
            res.add(new ArrayList<>(path));
            return;
        }
    
        path.add(start);
        this.dfs.accept(start + 1, n, k, path, res);
        path.removeLast();
        this.dfs.accept(start + 1, n, k, path, res);
    };

public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> res = new ArrayList<>();

    this.dfs.accept(1, n, k, new ArrayList<>(), res);

    return res;
}

Approach 3: Combination Enum(Iteration Impl)

pub fn combine(n: i32, k: i32) -> Vec<Vec<i32>> {
    let mut res = vec![];
    let mut path = (1..=k)
        .into_iter()
        .fold(Vec::with_capacity(k + 1), |mut path, val| {
            path.push(val as i32);
            path
        });
    path.push(n + 1);

    let mut j = 0;
    while j < k {
        res.push(path[..k].to_vec());

        j = 0;
        while j < k && path[j] + 1 == path[j + 1] {
            path[j] = j as i32 + 1;
            j += 1;
        }

        path[j] += 1;
    }

    res
}

public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>(k + 1);
    for (int i = 1; i <= k; i++) {
        path.add(i);
    }
    path.add(n + 1);

    int j = 0;
    while (j < k) {
        res.add(new ArrayList<>(path.subList(0, k)));

        j = 0;
        while (j < k && path.get(j) + 1 == path.get(j + 1)) {
            path.set(j, j + 1);
            j++;
        }
        
        path.set(j, path.get(j) + 1);
    }

    return res;
}