CareerCup

Algorithm goes as follows-

start from the beginning of the array and keep on pushing element's index to another array(taken array) and subtract target with the array element keeping account of count of elements of `taken` array.
Do this recursively for each element. At the time when you identify that target is 0, print all the elements in `taken` array.
Just skip incase target becomes -ve.

Below is the successful running code.

Happy coding!!

#include<iostream>
using namespace std;


void PrintAllSumCombos(int arr[], int target,int start,int taken[],int count) {
if (target==0) {
for (int i =0;i<count;i++) {
cout << taken[i] << " ";
}
cout << "\n";
return ;
}
if (target ==-1 || start > 7) {
return ;
}
for(int i=start; i < 7 ;i++) {
taken[count]=i;
PrintAllSumCombos(arr,target-arr[i],i+1,taken,count+1);
}



}
int main() {

int a[7]={1, 7, 3, 4, 5, 6, 2};
int b[7];
PrintAllSumCombos(a, 7,0,b,0) ;

return 0;
}

@Jeanclaude

Will the input array always have numbers between 1 and n?

simple backtracking! just add numbers to a sum and if it reaches the target, then you print; if it goes over the target... go back ( backtrack ) and if its lower and you still got number to be addin' add and repeat :)

#include<stdio.h>
#include<stdlib.h>
int s=0;
Combination(int *a,int n,int *out,int i,int pos,int sum){
	int k,j;
	if(pos==n)return;
	for(k=i;k<n;k++){
		out[pos]=k;
		s=s+a[k];
		if(s==sum){
			out[pos+1]=-1;
			for(j=0;j<n&&out[j]!=-1;j++)
				printf("%d  ",out[j]);
			printf("\n");
		}
		//printf("\n");
		Combination(a,n,out,k+1,pos+1,sum);	
		s=s-a[k];
	}
}
main(){
	int *a,n,givensum,j,*out;
	printf("Enter the array size");
	scanf("%d" ,&n);
	a=(int *)malloc(sizeof(int)*n);
	for(j=0;j<n;j++)
		scanf("%d",&a[j]);
	printf("Enter the sum");
	scanf("%d",&givensum);
	out=(int *)malloc(sizeof(int)*n);
	Combination(a,n,out,0,0,givensum);
}

Basically recursion is used below but I think Dynamic programming approach is also good but that takes a lot of space.

int a[] = {1, 2, 3, 4, 5, 6, 7};

int k=0;
int visited[100]={0};

void subset_sum(int i, int target)
{
        if((i >= sizeof(a)/sizeof(a[0])) || i < 0 || target < 0){
                return;
        }
        if(target == 0) {
                int j;
                for(j=0;j<sizeof(a)/sizeof(a[0]);j++)
                        if(visited[j] == 1)
                                printf("%4d", j);
                printf("\n");
                return;
        }
        visited[i] = 1;
        subset_sum(i+1, target-a[i]);
        visited[i] = 0;
        subset_sum(i+1, target);
}

int main()
{
        subset_sum(0, 10);
}

#include<stdio.h>
main()
{
int a[10],i,j,k,sum;
printf("enter the sum : \n");
scanf("%d",&sum);
printf("Enter the elements of array : \n");
for(i=0;i<10;i++)
scanf("%d",&a[i]);
for(i=0;i<10;i++)
{
for(j=0;j<10;j++)
{
for(k=0;k<10;k++)
{
if((i!=j) && (i!=k) && (j!=k) && (a[i]+a[j]+a[k] == sum))
printf("%d\t%d\t%d\n",i,j,k);
}
}
}
}

sites.google.com/site/spaceofjameschen/home/recursion/print-the-indices-of-all-the-combination

Python:
I'm using itertools.combinations to find combinations of a given list. If i cant use these modules, this function can be replaced by a user defined function.

import itertools 
        
def getindices(tlist, n):
    clist = []
    if n in tlist:
        clist.append(tlist.index(n))
    for i in xrange(2, len(tlist)+1):
        for c in itertools.combinations(tlist, i):
            if sum(c) == n:
                clist.append(map(lambda n: tlist.index(n[1], n[0]), \
                                 enumerate(c)))
    for each in clist[:]:
        if clist.count(each) > 1 or \
           type(each) is list and clist.count(each[::-1]) > 1:
            clist.remove(each)
    return clist


Testing:
tlist = [1, 7, 3, 4, 5, 6, 2]
for i in xrange(1, len(tlist)+1):
    print i, '==>', getindices(tlist, i)

1 ==> [0]
2 ==> [6]
3 ==> [2, [0, 6]]
4 ==> [3, [0, 2]]
5 ==> [4, [0, 3], [2, 6]]
6 ==> [5, [0, 4], [3, 6], [0, 2, 6]]
7 ==> [1, [0, 5], [2, 3], [4, 6], [0, 3, 6]]

//import java.util.Scanner;
public class {
public static void x(int y[], int t) {
for (int i = 0; i < y.length; i++) {
for (int j = i; j < y.length; j++) {
for (int k = j; k < y.length; k++) {
if (y[i] + y[j] + y[k] == t && i != j && i != k && j != k) {
System.out.println(i + "," + j + "," + k + "");
}
}
}
}
for (int i = 0; i < y.length; i++) {
if (y[i] == t) {
System.out.println(i);
}
}
for (int i = 0; i < y.length; i++) {
for (int j = i; j < y.length; j++) {
if (y[i] + y[j] == t) {
System.out.println(i + "," + j );
}
}
}

}
public static void main(String[] args) {
x(new int [] {1, 7, 3, 4, 5, 6, 2}, 7);
}
}

Naive solution but it works well enough:

def adds_to(list, target)
	return [] if list.nil? or list.empty? or target <= 0
	return target == list.first ? [[0]] : [] if list.size == 1

	result = []
	list.each_with_index do |e, i|
		if e == target
			result << [i]
			next
		end
		
		indices = adds_to(list[i + 1 .. list.size - 1], target - e)
		next if indices.empty?
		indices = indices.map {|a| [i] + a.map{ |x| x + i + 1}}
		result += indices
	end
	
	return result
end

puts adds_to([1,2,3], 3).inspect
# Prints [[0, 1], [2]]