CercaLeSomme

gistfile1.cpp

//
//  main.cpp
//  CercaLeSomme
//
//  Created by Ale on 12/04/15.
//  Copyright (c) 2015 ABeltramo. All rights reserved.
//

#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

int valFinale; //Valore che voglio ottenere
int NElementi; //Numero di cifre totali
vector<int> Input; //Vettore che contiene i numeri che mi passa
vector<bool> Soluzione; //Contiene le posizioni dove bisogna mettere il +


/*
 * Presi due interi A e B restituisce AB
 */
int concatenaInt(int a, int b){
	int base = 1;
	while(base <= b)
		base *= 10;
	return (base * a) +b;
}


/*
 * Funzione ricorsiva:
 * mi genera tutte le possibili combinazioni di + che posso ottenere
 * Per ogni combinazione mi controlla se la somma dei numeri con quella combo
 * mi da il valore che cerco
 * In quel caso stampo
 */
void trovaSoluzione(int pos){
	if(pos >= NElementi - 1){ //Passo base
		//Sono arrivato in fondo ad una sequenza
		//Controllo se questa sequenza di + mi porta alla soluzione corretta
		int ris = 0; //Risultato intermedio
		int pre = Input[0]; //Numero precedente
		for(int i=0;i<NElementi-1;i++){ //NElementi-1 perchè ci sono N-1 + nella sequenza
			if(Soluzione[i]){ //Ho messo un + quindi sommo il precedente
				ris += pre;
				pre = Input[i+1];
			}
			else{ // Non ho messo un + quindi devo concatenare
				pre = concatenaInt(pre,Input[i+1]);
			}
		}
		if(ris + pre == valFinale){ //Se ottengo il valore che cerco lo stampo
			for(int i=0;i<NElementi-1;i++){
				if(Soluzione[i])
					cout << i+1 << " ";
			}
			cout << endl;
		}
	}
	else{ //Passo ricorsivo
		Soluzione[pos] = true;
		trovaSoluzione(pos+1); //Uso il +
		
		Soluzione[pos] = false;
		trovaSoluzione(pos+1); //Non uso il +
	}
}


/*
 * MAIN()
 */
int main() {
	ifstream inFile("input.txt");
	inFile >> NElementi;
	for(int i=0;i<NElementi;i++){
		int ele;
		inFile >> ele;
		Input.push_back(ele);
	}
	inFile >> valFinale;
	inFile.close();
	
	/*
	 * FINE LETTURA DAL FILE
	 */
	
	Soluzione.resize(NElementi); //Lo rendo della dimensione appropriata
	trovaSoluzione(0);
	
    return 0;
}