Combination Sum Iii

                                            
class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> res;
        vector<int> cur;
        backtrack(res, cur, 1, k, n);
        return res;
    }
    
    void backtrack(vector<vector<int>>& res, vector<int>& cur, int start, int k, int n) {
        if (k == 0 && n == 0) {
            res.push_back(cur);
            return;
        }
        
        for (int i = start; i <= 9; ++i) {
            cur.push_back(i);
            backtrack(res, cur, i + 1, k - 1, n - i);
            cur.pop_back();
        }
    }
};

                                            
class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> current = new ArrayList<>();
        backtrack(result, current, k, n, 1);
        return result;
    }

    private void backtrack(List<List<Integer>> result, List<Integer> current, int k, int n, int start) {
        if (n == 0 && k == 0) {
            result.add(new ArrayList<>(current));
            return;
        }

        for (int i = start; i <= 9; i++) {
            if (n - i < 0 || k - 1 < 0) {
                break;
            }
            current.add(i);
            backtrack(result, current, k - 1, n - i, i + 1);
            current.remove(current.size() - 1);
        }
    }
}

                                            
class Solution(object):
    def combinationSum3(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: List[List[int]]
        """
        def backtrack(start, k, n, path, res):
            if k == 0 and n == 0:
                res.append(path)
                return
            if k < 0 or n < 0:
                return
            for i in range(start, 10):
                backtrack(i + 1, k - 1, n - i, path + [i], res)
        
        res = []
        backtrack(1, k, n, [], res)
        return res

                                            
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as 
 * returnColumnSizes array.
 */
void combinationSum3Helper(int k, int n, int start, int count, int *temp, int **result, int *returnSize, int **returnColumnSizes) {
    if (n == 0 && count == k) {
        result[*returnSize] = (int *)malloc(k * sizeof(int));
        memcpy(result[*returnSize], temp, k * sizeof(int));
        (*returnColumnSizes)[*returnSize] = k;
        (*returnSize)++;
        return;
    }

    for (int i = start; i <= 9; i++) {
        temp[count] = i;
        combinationSum3Helper(k, n - i, i + 1, count + 1, temp, result, returnSize, returnColumnSizes);
    }
}

int **combinationSum3(int k, int n, int *returnSize, int **returnColumnSizes) {
    *returnSize = 0;
    int **result = (int **)malloc(1000 * sizeof(int *));
    *returnColumnSizes = (int *)malloc(1000 * sizeof(int));
    int temp[10];
    combinationSum3Helper(k, n, 1, 0, temp, result, returnSize, returnColumnSizes);
    return result;
}

                                            
public class Solution {
    public IList<IList<int>> CombinationSum3(int k, int n) {
        IList<IList<int>> result = new List<IList<int>>();
        List<int> current = new List<int>();
        Backtrack(result, current, k, n, 1);
        return result;
    }
    
    private void Backtrack(IList<IList<int>> result, List<int> current, int k, int target, int start) {
        if (k == 0 && target == 0) {
            result.Add(new List<int>(current));
            return;
        }
        
        for (int i = start; i <= 9; i++) {
            current.Add(i);
            Backtrack(result, current, k - 1, target - i, i + 1);
            current.RemoveAt(current.Count - 1);
        }
    }
}

                                            
/**
 * @param {number} k
 * @param {number} n
 * @return {number[][]}
 */
const combinationSum3 = (k, n) => {
    const result = [];
    
    const backtrack = (start, k, n, path) => {
        if (k === 0 && n === 0) {
            result.push([...path]);
            return;
        }
        if (k === 0 || n === 0) {
            return;
        }
        
        for (let i = start; i <= 9; i++) {
            path.push(i);
            backtrack(i + 1, k - 1, n - i, path);
            path.pop();
        }
    };
    
    backtrack(1, k, n, []);
    
    return result;
};

                                            
function combinationSum3(k: number, n: number): number[][] {
    const results: number[][] = [];
    
    function backtrack(start: number, target: number, current: number, path: number[]) {
        if (target === 0 && path.length === k) {
            results.push([...path]);
            return;
        }
        
        for (let i = start; i <= 9; i++) {
            if (current + i > n || path.length >= k) {
                return;
            }
            path.push(i);
            backtrack(i + 1, target - i, current + i, path);
            path.pop();
        }
    }
    
    backtrack(1, n, 0, []);
    
    return results;
}

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

                                            
class Solution {
    fun combinationSum3(k: Int, n: Int): List<List<Int>> {
        val result = mutableListOf<List<Int>>()
        backtrack(k, n, 1, mutableListOf(), result)
        return result
    }

    private fun backtrack(k: Int, target: Int, start: Int, path: MutableList<Int>, result: MutableList<List<Int>>) {
        if (k == 0 && target == 0) {
            result.add(path.toList())
            return
        }
        
        for (i in start..9) {
            if (i > target) break
            path.add(i)
            backtrack(k - 1, target - i, i + 1, path, result)
            path.removeAt(path.size - 1)
        }
    }
}

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

                                            
func combinationSum3(k int, n int) [][]int {
    var result [][]int
    var path []int
    backtrack(&result, &path, k, n, 1)
    return result
}

func backtrack(result *[][]int, path *[]int, k, n, start int) {
    if k == 0 && n == 0 {
        tmp := make([]int, len(*path))
        copy(tmp, *path)
        *result = append(*result, tmp)
        return
    }
    if k == 0 || n == 0 {
        return
    }

    for i := start; i <= 9; i++ {
        *path = append(*path, i)
        backtrack(result, path, k-1, n-i, i+1)
        *path = (*path)[:len(*path)-1]
    }
}

                                            
# @param {Integer} k
# @param {Integer} n
# @return {Integer[][]}
def combination_sum3(k, n)
    result = []
    dfs(k, n, 1, [], result)
    result
end

def dfs(k, n, start, path, result)
    if k == 0 && n == 0
        result << path.dup
        return
    end
    
    return if k == 0 || n == 0
    
    (start..9).each do |num|
        path << num
        dfs(k - 1, n - num, num + 1, path, result)
        path.pop
    end
end

                                            
object Solution {
    def combinationSum3(k: Int, n: Int): List[List[Int]] = {
        var res = List[List[Int]]()
        
        def backtrack(k: Int, n: Int, start: Int, path: List[Int]): Unit = {
            if (k == 0 && n == 0) {
                res = path :: res
            } else {
                for (i <- start to 9) {
                    backtrack(k - 1, n - i, i + 1, i :: path)
                }
            }
        }
        
        backtrack(k, n, 1, List())
        res
    }
}

                                            
impl Solution {
    pub fn combination_sum3(k: i32, n: i32) -> Vec<Vec<i32>> {
        let mut result = Vec::new();
        let mut current = Vec::new();
        Self::backtrack(1, k, n, &mut current, &mut result);
        result
    }

    fn backtrack(start: i32, k: i32, target: i32, current: &mut Vec<i32>, result: &mut Vec<Vec<i32>>) {
        if target == 0 && k == 0 {
            result.push(current.clone());
            return;
        }

        if target < 0 || k == 0 {
            return;
        }

        for i in start..=9 {
            current.push(i);
            Self::backtrack(i + 1, k - 1, target - i, current, result);
            current.pop();
        }
    }
}

To solve this coding challenge, it is critical to employ a backtracking approach because it allows us to explore all possible combinations efficiently while pruning invalid paths early. We will explore each number from 1 to 9, building combinations iteratively, and ensure that no number is used more than once in any combination. If at any point, the sum of the current combination exceeds the target sum

n

or the number of elements exceeds

k

, we can backtrack—thus excluding the current path from further consideration.

Explanation

Define the Problem:

We need to find all combinations of
k

unique numbers that sum up to
n

.
Only numbers from 1 to 9 can be used.
Each number can be used at most once in each combination.

Constraints to Observe:

We need exactly
k

elements in each combination.
The sum of these
k

elements should be exactly
n

.
All elements should be unique and range from 1 to 9.

Backtracking Strategy:

We will use a function
backtrack

that starts from a given number and builds potential combinations recursively.
If the current combination has exactly
k

elements, we check if the sum equals
n

. If so, it's a valid combination.
If not, we continue to add elements until the combination exceeds the length
k

or its sum exceeds
n

.

Initial Setup:

Start with an empty combination and the starting number set to 1.
Use a list
res

to store all valid combinations.

Termination Conditions:

If
k

elements are picked and their sum equals
n

, store the combination.
If the combination length exceeds
k

or sum exceeds
n

, discard that path.

Iterative Process:

For each number
i

from the current start number to 9:

Add
i

to the current combination.
Recur with the next number (
i + 1

), reduce
k

by 1 (since we have picked one element), and adjust
n

by subtracting
i

.
Backtrack by removing the last element and exploring further possibilities.

Pseudocode

Initial Setup

                                            
# Function to find all valid combinations
function combinationSum3(k, n):
result_list = []  # To store all valid combinations

# Backtracking function to build combinations
function backtrack(start, k, n, current_combination):
if k == 0 and n == 0:
# Valid combination found
add current_combination to result_list
return

if k < 0 or n < 0:
# Combination is invalid, end path
return

# Explore all possible numbers from start to 9
for i in range from start to 10:
# Include current number in combination
new_combination = current_combination + [i]

# Recur with next number, reduced k, and adjusted n
backtrack(i + 1, k - 1, n - i, new_combination)

# Start backtracking with initial conditions
backtrack(1, k, n, [])

return result_list

Detailed Steps in Pseudocode

Starting Point

Initialize the Result List:

Create an empty list
result_list

to store the valid combinations that meet the criteria.

Define the Backtracking Function:

This function
backtrack

will handle the recursive building of combinations by iterating through possible numbers.
It takes parameters including the starting number (
start

), remaining number count (
k

), remaining sum (
n

), and the current combination being built (
current_combination

).

Backtracking and Generating Combinations

Check for Valid Combination:

If
k

is 0 and
n

is also 0, it means we've found a valid combination.
Add the current path
current_combination

to
result_list

.

Prune Invalid Paths Early:

If
k

is less than 0 or
n

is less than 0 (exceeding the required number count or sum), terminate this path.

Iterate Through Numbers:

Iterate the numbers from
start

to 9 because we're only interested in numbers between 1 and 9.
For each number
i

in this range, add it to the current combination.

Recurrence and Backtracking

Recursive Call and Pruning:

Make a recursive call to
backtrack

with the next starting number (
i + 1

), decrement
k

by 1 (because we picked one more number), and adjust
n

by subtracting
i

.
This keeps the process moving forward by exploring potential combinations.

Return Final Result:

Return
result_list

after all combinations have been considered.

By following this comprehensive backtracking strategy, we ensure that the solution explores all possible valid combinations without redundancy or inefficiencies.