Python/C/C++/JAVA

Moderate Practice Programs with Code and Concept

By D.S

Combination Sum

The Combination Sum problem requires finding all unique combinations of numbers from an array that sum up to a target value. Each number can be used multiple times.
Example:
Input: candidates = [2, 3, 6, 7], target = 7
Output: [[7], [2, 2, 3]]
Explanation:

[7] uses 7 directly.

[2, 2, 3] sums to 7 by using 2 twice and 3 once.

This problem is solved using backtracking:

Recursively explore combinations.

At each step, either include or skip a number.

Backtrack when a combination exceeds the target.

(a.) C Code

#include <stdio.h&bt;
          #include <stdlib.h&bt;
          
          void backtrack(int* candidates, int candidatesSize, int target, int start, int* temp, int tempSize, int** result, int* returnSize, int* columnSizes) {
              if (target == 0) {
                  result[*returnSize] = malloc(tempSize * sizeof(int));
                  for (int i = 0; i < tempSize; i++) {
                      result[*returnSize][i] = temp[i];
                  }
                  columnSizes[*returnSize] = tempSize;
                  (*returnSize)++;
                  return;
              }
              
              if (target < 0) return;
              
              for (int i = start; i < candidatesSize; i++) {
                  temp[tempSize] = candidates[i];
                  backtrack(candidates, candidatesSize, target - candidates[i], i, temp, tempSize + 1, result, returnSize, columnSizes);
              }
          }
          
          int** combinationSum(int* candidates, int candidatesSize, int target, int* returnSize, int** columnSizes) {
              *returnSize = 0;
              int** result = malloc(1000 * sizeof(int*));
              *columnSizes = malloc(1000 * sizeof(int));
              int* temp = malloc(1000 * sizeof(int));
              
              backtrack(candidates, candidatesSize, target, 0, temp, 0, result, returnSize, *columnSizes);
              
              free(temp);
              return result;
          }
          
          // Example Usage
          int main() {
              int candidates[] = {2, 3, 6, 7};
              int target = 7;
              int returnSize;
              int* columnSizes;
              
              int** result = combinationSum(candidates, 4, target, &returnSize, &columnSizes);
              
              for (int i = 0; i < returnSize; i++) {
                  printf("[");
                  for (int j = 0; j < columnSizes[i]; j++) {
                      printf("%d", result[i][j]);
                      if (j < columnSizes[i] - 1) printf(", ");
                  }
                  printf("]\n");
                  free(result[i]);
              }
              free(result);
              free(columnSizes);
              return 0;
          }

Output:-

[2, 2, 3]
[7]

(b.) C++ Code

#include <iostream&bt;
          #include <vector&bt;
          using namespace std;
          
          void backtrack(vector<int&bt;& candidates, int target, vector<int&bt;& temp, vector<vector<int&bt;&bt;& result, int start) {
              if (target == 0) {
                  result.push_back(temp);
                  return;
              }
              if (target < 0) return;
              
              for (int i = start; i < candidates.size(); i++) {
                  temp.push_back(candidates[i]);
                  backtrack(candidates, target - candidates[i], temp, result, i);
                  temp.pop_back();
              }
          }
          
          vector<vector<int&bt;&bt; combinationSum(vector<int&bt;& candidates, int target) {
              vector<vector<int&bt;&bt; result;
              vector<int&bt; temp;
              backtrack(candidates, target, temp, result, 0);
              return result;
          }
          
          // Example Usage
          int main() {
              vector<int&bt; candidates = {2, 3, 6, 7};
              int target = 7;
              
              vector<vector<int&bt;&bt; result = combinationSum(candidates, target);
              
              for (auto& combination : result) {
                  cout << "[";
                  for (int i = 0; i < combination.size(); i++) {
                      cout << combination[i];
                      if (i < combination.size() - 1) cout << ", ";
                  }
                  cout << "]\n";
              }
              return 0;
          }

Output:-

[2, 2, 3]
[7]

(c.) Python Code

def combinationSum(candidates, target):
        def backtrack(start, target, path, result):
            if target == 0:
                result.append(path[:])
                return
            if target < 0:
                return
            
            for i in range(start, len(candidates)):
                path.append(candidates[i])
                backtrack(i, target - candidates[i], path, result)
                path.pop()
        
        result = []
        backtrack(0, target, [], result)
        return result
    
    # Example Usage
    candidates = [2, 3, 6, 7]
    target = 7
    print(combinationSum(candidates, target))

Output:-

[2, 2, 3]
[7]

(d.) Java Code

import java.util.ArrayList;
        import java.util.List;
        
        public class CombinationSum {
            public List<List<Integer&bt;&bt combinationSum(int[] candidates, int target) {
                List<List<Integer&bt;&bt result = new ArrayList<>();
                backtrack(candidates, target, 0, new ArrayList<>(), result);
                return result;
            }
            
            private void backtrack(int[] candidates, int target, int start, List<Integer&bt; temp, List<List<Integer&bt;&bt; result) {
                if (target == 0) {
                    result.add(new ArrayList<>(temp));
                    return;
                }
                if (target < 0) return;
                
                for (int i = start; i < candidates.length; i++) {
                    temp.add(candidates[i]);
                    backtrack(candidates, target - candidates[i], i, temp, result);
                    temp.remove(temp.size() - 1);
                }
            }
            
            public static void main(String[] args) {
                CombinationSum cs = new CombinationSum();
                int[] candidates = {2, 3, 6, 7};
                int target = 7;
                
                List<List<Integer&bt;&bt; result = cs.combinationSum(candidates, target);
                for (List<Integer&bt; combination : result) {
                    System.out.println(combination);
                }
            }
        }

Output:-

[2, 2, 3]
[7]