Combinations

                                            
class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        vector<int> temp;
        backtrack(res, temp, n, k, 1);
        return res;
    }
    
    void backtrack(vector<vector<int>>& res, vector<int>& temp, int n, int k, int start) {
        if (temp.size() == k) {
            res.push_back(temp);
            return;
        }
        
        for (int i = start; i <= n; i++) {
            temp.push_back(i);
            backtrack(res, temp, n, k, i + 1);
            temp.pop_back();
        }
    }
};

                                            
class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> current = new ArrayList<>();
        backtrack(result, current, 1, n, k);
        return result;
    }
    
    private void backtrack(List<List<Integer>> result, List<Integer> current, int start, int n, int k) {
        if (current.size() == k) {
            result.add(new ArrayList<>(current));
            return;
        }
        
        for (int i = start; i <= n; i++) {
            current.add(i);
            backtrack(result, current, i + 1, n, k);
            current.remove(current.size() - 1);
        }
    }
}

                                            
class Solution(object):
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        def backtrack(start, path):
            if len(path) == k:
                output.append(path)
                return
            for i in range(start, n+1):
                backtrack(i+1, path + [i])

        output = []
        backtrack(1, [])
        return output

                                            
public class Solution {
    public IList<IList<int>> Combine(int n, int k) {
        IList<IList<int>> result = new List<IList<int>>();
        List<int> current = new List<int>();
        Backtrack(result, current, 1, n, k);
        return result;
    }

    private void Backtrack(IList<IList<int>> result, List<int> current, int start, int n, int k) {
        if (k == 0) {
            result.Add(new List<int>(current));
            return;
        }

        for (int i = start; i <= n; i++) {
            current.Add(i);
            Backtrack(result, current, i + 1, n, k - 1);
            current.RemoveAt(current.Count - 1);
        }
    }
}

                                            
/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function(n, k) {
    const result = [];
    
    const backtrack = (curr, start) => {
        if (curr.length === k) {
            result.push(curr.slice());
            return;
        }
        
        for (let i = start; i <= n; i++) {
            curr.push(i);
            backtrack(curr, i + 1);
            curr.pop();
        }
    }
    
    backtrack([], 1);
    return result;
};

                                            
function combine(n: number, k: number): number[][] {
    const result: number[][] = [];
    
    const backtrack = (start: number, curr: number[]) => {
        if (curr.length === k) {
            result.push([...curr]);
            return;
        }
        
        for (let i = start; i <= n; i++) {
            curr.push(i);
            backtrack(i + 1, curr);
            curr.pop();
        }
    };
    
    backtrack(1, []);
    
    return result;
};

                                            
class Solution {
    /**
     * @param Integer $n
     */
    function combine($n, $k) {
        $answer = [];
        $this->backtrack($n, $k, 1, [], $answer);
        return $answer;
    }
    
    function backtrack($n, $k, $start, $path, &$answer) {
        if ($k === 0) {
            $answer[] = $path;
            return;
        }
        
        for ($i = $start; $i <= $n; $i++) {
            $path[] = $i;
            $this->backtrack($n, $k - 1, $i + 1, $path, $answer);
            array_pop($path);
        }
    }
}

                                            
class Solution {
    fun combine(n: Int, k: Int): List<List<Int>> {
        val result = mutableListOf<List<Int>>()
        val tempList = mutableListOf<Int>()

        fun backtrack(start: Int, tempList: MutableList<Int>) {
            if (tempList.size == k) {
                result.add(tempList.toList())
                return
            }

            for (i in start..n) {
                tempList.add(i)
                backtrack(i + 1, tempList)
                tempList.removeAt(tempList.size - 1)
            }
        }

        backtrack(1, tempList)
        return result
    }
}

                                            
class Solution {
  List<List<int>> combine(int n, int k) {
    List<List<int>> result = [];
    
    void backtrack(int start, List<int> curr) {
      if (curr.length == k) {
        result.add(List.from(curr));
        return;
      }
      
      for (int i = start; i <= n; i++) {
        curr.add(i);
        backtrack(i + 1, curr);
        curr.removeLast();
      }
    }
    
    backtrack(1, []);
    
    return result;
  }
}

                                            
func combine(n int, k int) [][]int {
    res := [][]int{}
    
    var backtrack func(start int, path []int)
    backtrack = func(start int, path []int) {
        if len(path) == k {
            temp := make([]int, k)
            copy(temp, path)
            res = append(res, temp)
            return
        }
        
        for i := start; i <= n; i++ {
            backtrack(i+1, append(path, i))
        }
    }
    
    backtrack(1, []int{})
    
    return res
}

                                            
# @param {Integer} n
# @param {Integer} k
# @return {Integer[][]}
def combine(n, k)
    result = []
    current = []
    
    backtrack(1, n, k, current, result)
    
    result
end

def backtrack(start, n, k, current, result)
    if current.length == k
        result << current.dup
        return
    end
    
    (start..n).each do |num|
        current << num
        backtrack(num + 1, n, k, current, result)
        current.pop
    end
end

                                            
object Solution {
    def combine(n: Int, k: Int): List[List[Int]] = {
        if (k == 0) {
            List(List())
        } else if (k == n) {
            (1 to n).toList  :: Nil
        } else {
            combine(n - 1, k) ++ combine(n - 1, k - 1).map(_ :+ n)
        }
    }
}

                                            
impl Solution {
    pub fn combine(n: i32, k: i32) -> Vec<Vec<i32>> {
        let mut result = Vec::new();
        let mut path = Vec::new();
        
        fn backtrack(start: i32, n: i32, k: i32, path: &mut Vec<i32>, result: &mut Vec<Vec<i32>>) {
            if path.len() == k as usize {
                result.push(path.clone());
                return;
            }
            
            for i in start..=n {
                path.push(i);
                backtrack(i + 1, n, k, path, result);
                path.pop();
            }
        }
        
        backtrack(1, n, k, &mut path, &mut result);
        
        result
    }
}

                                            
-spec combine(N :: integer(), K :: integer()) -> 
[[integer()]].
combine(N, K) ->
    combine(N, K, lists:seq(1, N)).

combine(_, 0, _) ->
    [[]];
combine(N, K, [H|T]) ->
    [[H|X] || X <- combine(N, K-1, T)] ++ combine(N, K, T);
combine(_, _, []) ->
    [].

To solve this coding challenge, we need to generate all possible combinations of k numbers chosen from the range [1, n]. The combinations are considered unordered, meaning that the combination [1, 2] is the same as [2, 1]. Therefore, we must ensure that each combination is unique.

Explanation

This problem can be solved using a backtracking approach. Backtracking is a systematic method for generating all possible combinations of elements that satisfy certain criteria. In this case, we need to generate combinations of k elements from the range [1, n]. Here’s a step-by-step explanation of the approach:

Initialization : We start by initializing an empty list called
output

to store the final list of combinations.
Backtrack Function : We define a helper function
backtrack

that will generate the combinations. This function will take two parameters:

start

: The starting number for the current combination.
path

: The current combination being built.

Base Case : Inside the
backtrack

function, we first check if the length of the current combination (
path

) is equal to
k

. If it is, we add this combination to the
output

list and return, since we have completed a valid combination.
Recursive Case : If the current combination is not complete, we iterate from the
start

number to
n

. For each number in this range, we add the number to the current combination (
path

) and make a recursive call to
backtrack

with the next start number as
i + 1

(to avoid duplicate combinations). After the recursive call, we proceed with the next iteration.
Starting the Backtracking Process : Finally, we start the backtracking process by calling the
backtrack

function initially with
start

as 1 and an empty combination (
path

).
Return Result : After all possible combinations have been generated, we return the
output

list.

Let’s translate this approach into detailed pseudocode with comments explaining each step:

                                            
# Define the function to generate combinations
Function generate_combinations(n, k)
# Initialize the output list to store all combinations
output = []

# Define the helper function for backtracking
Function backtrack(start, path)
# Base case: if the length of the current combination is equal to k
If length(path) == k
# Add the current combination to the output list
Add path to output
Return
End If

# Iterate from the start number to n
For i from start to n
# Add the current number to the combination
new_path = path + [i]
# Make a recursive call to continue building the combination
backtrack(i + 1, new_path)
End For
End Function

# Start the backtracking process from 1 and with an empty combination
backtrack(1, [])

# Return the final list of combinations
Return output
End Function

Detailed Steps in Pseudocode

Initialize an empty list
output

to store the combinations.
Define a function
backtrack(start, path)

to handle recursive backtracking.

Check if the length of
path

equals
k

.

If so, add
path

to
output

and return.

Iterate from
start

to
n

.

Append the current number
i

to
path

.
Call
backtrack

recursively with
i + 1

and the updated
path

.

Start the backtracking process by calling
backtrack(1, [])

.
Return the
output

list containing all possible combinations.

By following these steps and utilizing the backtracking technique, the challenge can be efficiently solved. The constraints (1 ≤ n ≤ 20 and 1 ≤ k ≤ n) ensure that the computational requirements are manageable within these bounds.