Problem Statement:
Given an array of distinct integers and a target integer, find all unique combinations in the array where the numbers sum to the target. You may use the same number multiple times. The numbers in each combination should be in non-descending order, and the combinations themselves should be unique.
Approach:
- Backtracking:
- Use recursion to explore all possible combinations of numbers.
- Maintain a running sum and a combination list.
- If the running sum equals the target, store the combination.
- If the running sum exceeds the target, stop exploring further.
- Avoid duplicate combinations by ensuring each recursive call starts from the current number.
- Sorting:
- Sort the input array to facilitate skipping duplicate numbers and ensure combinations are in non-descending order.
- Output:
- Return a list of lists, where each list represents a valid combination.
Examples:
Input: arr[] = 2, 4, 6, 8, x = 8
Output:Â
[2, 2, 2, 2]
[2, 2, 4]
[2, 6]
[4, 4]
[8]Code Implementations:
Java:
import java.util.ArrayList;
import java.util.List;
public class CombinationSum {
public static List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
backtrack(candidates, target, 0, new ArrayList<>(), result);
return result;
}
private static void backtrack(int[] candidates, int target, int start, List<Integer> combination, List<List<Integer>> result) {
if (target == 0) {
result.add(new ArrayList<>(combination));
return;
}
for (int i = start; i < candidates.length; i++) {
if (candidates[i] > target) continue;
combination.add(candidates[i]);
backtrack(candidates, target - candidates[i], i, combination, result);
combination.remove(combination.size() - 1);
}
}
public static void main(String[] args) {
int[] candidates = {2, 3, 6, 7};
int target = 7;
List<List<Integer>> result = combinationSum(candidates, target);
System.out.println(result);
}
}
Python:
def combination_sum(candidates, target):
result = []
def backtrack(remaining, combination, start):
if remaining == 0:
result.append(list(combination))
return
for i in range(start, len(candidates)):
if candidates[i] > remaining:
continue
combination.append(candidates[i])
backtrack(remaining - candidates[i], combination, i)
combination.pop()
candidates.sort()
backtrack(target, [], 0)
return result
# Example usage:
candidates = [2, 3, 6, 7]
target = 7
print(combination_sum(candidates, target))
C#:
using System;
using System.Collections.Generic;
class CombinationSum {
public static IList<IList<int>> CombinationSumMethod(int[] candidates, int target) {
IList<IList<int>> result = new List<IList<int>>();
Array.Sort(candidates);
Backtrack(candidates, target, 0, new List<int>(), result);
return result;
}
private static void Backtrack(int[] candidates, int target, int start, List<int> combination, IList<IList<int>> result) {
if (target == 0) {
result.Add(new List<int>(combination));
return;
}
for (int i = start; i < candidates.Length; i++) {
if (candidates[i] > target) continue;
combination.Add(candidates[i]);
Backtrack(candidates, target - candidates[i], i, combination, result);
combination.RemoveAt(combination.Count - 1);
}
}
public static void Main(string[] args) {
int[] candidates = { 2, 3, 6, 7 };
int target = 7;
var result = CombinationSumMethod(candidates, target);
foreach (var combo in result) {
Console.WriteLine(string.Join(", ", combo));
}
}
}
JavaScript:
function combinationSum(candidates, target) {
const result = [];
function backtrack(remaining, combination, start) {
if (remaining === 0) {
result.push([...combination]);
return;
}
for (let i = start; i < candidates.length; i++) {
if (candidates[i] > remaining) continue;
combination.push(candidates[i]);
backtrack(remaining - candidates[i], combination, i);
combination.pop();
}
}
candidates.sort((a, b) => a - b);
backtrack(target, [], 0);
return result;
}
// Example usage:
const candidates = [2, 3, 6, 7];
const target = 7;
console.log(combinationSum(candidates, target));
Example Input and Output:
Input:
candidates = [2, 3, 6, 7]
target = 7
Output:
plaintextCopy code[[2, 2, 3], [7]]
The provided implementations use backtracking to explore all possible combinations and ensure the results meet the problem’s requirements.
You said:
write in c,cpp
ChatGPT said:
ChatGPT
C Implementation
#include <stdio.h>
#include <stdlib.h>
void findCombinations(int* candidates, int n, int target, int* combination, int combIndex, int start) {
if (target == 0) {
// Print the current combination
for (int i = 0; i < combIndex; i++) {
printf("%d ", combination[i]);
}
printf("\n");
return;
}
for (int i = start; i < n; i++) {
if (candidates[i] > target) continue;
combination[combIndex] = candidates[i];
findCombinations(candidates, n, target - candidates[i], combination, combIndex + 1, i);
}
}
void combinationSum(int* candidates, int n, int target) {
int* combination = (int*)malloc(target * sizeof(int)); // Allocate memory for combinations
findCombinations(candidates, n, target, combination, 0, 0);
free(combination); // Free allocated memory
}
int main() {
int candidates[] = {2, 3, 6, 7};
int n = sizeof(candidates) / sizeof(candidates[0]);
int target = 7;
printf("Combinations that sum up to %d:\n", target);
combinationSum(candidates, n, target);
return 0;
}
C++ Implementation
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void findCombinations(vector<int>& candidates, int target, vector<int>& combination, int start, vector<vector<int>>& result) {
if (target == 0) {
result.push_back(combination);
return;
}
for (int i = start; i < candidates.size(); i++) {
if (candidates[i] > target) continue;
combination.push_back(candidates[i]);
findCombinations(candidates, target - candidates[i], combination, i, result);
combination.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> result;
vector<int> combination;
sort(candidates.begin(), candidates.end());
findCombinations(candidates, target, combination, 0, result);
return result;
}
int main() {
vector<int> candidates = {2, 3, 6, 7};
int target = 7;
vector<vector<int>> result = combinationSum(candidates, target);
cout << "Combinations that sum up to " << target << ":\n";
for (const auto& comb : result) {
for (int num : comb) {
cout << num << " ";
}
cout << endl;
}
return 0;
}