Combinations and Combination Sum: Backtracking Variants

def combinationSum(candidates, target):
    candidates.sort()  # optional but helps with pruning
    result = []
    def bt(start, current, remaining):
        if remaining == 0:
            result.append(current[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break  # pruning: sorted, no point continuing
            current.append(candidates[i])
            bt(i, current, remaining - candidates[i])  # i not i+1: reuse allowed
            current.pop()
    bt(0, [], target)
    return result

# Combination Sum II (no reuse, may have duplicates)
def combinationSum2(candidates, target):
    candidates.sort()
    result = []
    def bt(start, current, remaining):
        if remaining == 0:
            result.append(current[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining: break
            if i > start and candidates[i] == candidates[i-1]: continue  # skip dup
            current.append(candidates[i])
            bt(i + 1, current, remaining - candidates[i])
            current.pop()
    bt(0, [], target)
    return result

# Combination Sum III (exactly k numbers, 1-9, no reuse)
def combinationSum3(k, n):
    result = []
    def bt(start, current, remaining):
        if len(current) == k and remaining == 0:
            result.append(current[:])
            return
        if len(current) == k or remaining <= 0: return
        for i in range(start, 10):
            if i > remaining: break
            current.append(i)
            bt(i + 1, current, remaining - i)
            current.pop()
    bt(1, [], n)
    return result

# Standard nCr combinations
def combine(n, k):
    result = []
    def bt(start, current):
        if len(current) == k:
            result.append(current[:])
            return
        # Pruning: need k-len(current) more from [start..n]
        need = k - len(current)
        for i in range(start, n - need + 2):
            current.append(i)
            bt(i + 1, current)
            current.pop()
    bt(1, [])
    return result

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    sort(candidates.begin(), candidates.end());
    vector<vector<int>> result;
    vector<int> current;
    function<void(int, int)> bt = [&](int start, int rem) {
        if (rem == 0) { result.push_back(current); return; }
        for (int i = start; i < (int)candidates.size(); i++) {
            if (candidates[i] > rem) break;
            current.push_back(candidates[i]);
            bt(i, rem - candidates[i]);
            current.pop_back();
        }
    };
    bt(0, target);
    return result;
}

import java.util.*;

public class CombinationSum {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> result = new ArrayList<>();
        backtrack(candidates, target, 0, new ArrayList<>(), result);
        return result;
    }

    void backtrack(int[] cands, int rem, int start, List<Integer> curr, List<List<Integer>> result) {
        if (rem == 0) { result.add(new ArrayList<>(curr)); return; }
        for (int i = start; i < cands.length; i++) {
            if (cands[i] > rem) break;
            curr.add(cands[i]);
            backtrack(cands, rem - cands[i], i, curr, result);
            curr.remove(curr.size() - 1);
        }
    }
}