OJ Board

Code: Select all

#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;

int target = 0, sum = 0;
vector<bool> used(1005, false);
vector<int> v;

void recurse(int index){
	if(index == v.size()) return;
	if(sum + v[index] == target) {
		used[index] = true;
		bool flag = false;
		for(int i = 0; i<=index; ++i){
			if(!flag){
				if(used[i]) {
					printf("%d", v[i]);
					flag = true;
				}
				
			}
			else {
				if(used[i]) printf("+%d", v[i]);
			}
		}
		printf("\n");
		flag = false;
		sum = 0;
		used[index] = false;
		return;
	}
	if(sum + v[index] < target){
		used[index] = true;
		sum += v[index];
		recurse(index + 1);
		used[index] = false;
	}
	else{
		recurse(index + 1);	
	}
	
	
}

int main(){
	
	int count, temp;
	while(cin>>target>> count){
		if(!target && !count) return 0;
		
		for(int i = 0; i<count; ++i){
			cin>>temp;
			v.push_back(temp);
		}
		printf("Sums of %d:\n",target);
		for(int i = 0; i<v.size(); ++i){
			sum += v[i];
		}
		if(sum < target) {
			printf("NONE\n");
			sum = 0;
		}
		for(int i = 0; i<v.size(); ++i){
			sum = 0;
			//used[i] = true;
			recurse(i);
			//used[i] = false;
		}
		v.clear();
		sum = 0;
	}
	
	return 0;
}

Code: Select all

import java.util.ArrayList;
import java.util.Iterator;
import java.util.Scanner;

public class SumItUp {

	private int sum;
	private int size;
	private int[] arr;
	private boolean[] flag;
	
	private ArrayList<ArrayList<Integer>> set;
	
	public SumItUp(int sum, int size){
		this.size = size;
		this.sum = sum;
		
		this.arr = new int[size];
		this.flag = new boolean[size];
		
		this.set = new ArrayList<ArrayList<Integer>>();
		initializeFlag(0);
	}
	
	public void addValToArr(int index, int val){
		this.arr[index] = val;
	}
	
	public void initializeFlag(int init){
		
		for(int i=init;i<this.size;i++){
			this.flag[i] = false;
		}
	}
	
	public boolean checkSum(int cur, int val){
		
		if(this.arr[cur] > val){
			this.flag[cur] = false;
			
			if(cur + 1 < this.size)
				return checkSum(cur + 1, val);
			else
				return false;
		}
		
		else if(this.arr[cur] == val){
			this.flag[cur] = true;
			return true;
		}
		
		else{
			
			if(cur + 1 < this.size){
				boolean flag = false;
				this.flag[cur] = true;
				flag = checkSum(cur + 1, val - this.arr[cur]);
				
				if(flag)
					return flag;
				else{
					this.flag[cur] = false;
					flag = checkSum(cur + 1, val);
					return flag;
				}
			}
			else
				return false;
		}

	}
	
	public void printSet(){
		
		System.out.println("Sums of " + this.sum + ":");
		if(set.isEmpty()){
			System.out.println("NONE");
			return;
		}
		
		for(ArrayList<Integer> itArr : this.set){
			
			Iterator<Integer> itr = itArr.iterator();
			
			System.out.print(itr.next());
			while(itr.hasNext()){
				System.out.print("+" + itr.next());
			}
			System.out.println();
		}
		
	}
	
	public void addToSet(){
		
		ArrayList<Integer> cArr = new ArrayList<Integer>();
		int calcSum = 0;
		for(int i = 0; i < this.size;i++){
			if(flag[i] == true){
				cArr.add(this.arr[i]);
				calcSum += this.arr[i];
			}
		}
		
		if(!set.contains(cArr) && calcSum == this.sum){
			set.add(cArr);
		}
	}
	
	public void calculateSum(){
		
		int val =0;
		for(int i=0;i<this.size;i++){
			initializeFlag(0);
			val = this.sum;
			if(arr[i] > this.sum)
				continue;
			
			else if(arr[i] == this.sum){
				flag[i] = true;
				this.addToSet();
				
			}
			
			else {
				flag[i] = true;
				val = this.sum - this.arr[i];
			
				for(int j=i+1;j<this.size;j++){
					
					if(checkSum(j, val)){
						this.addToSet();
					}
				}
			}
		}
	} 
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner kb = new Scanner(System.in);
		
		SumItUp obj;
		int size = 0, sum = 0;
		int val;
		
		do{
			
			sum = kb.nextInt();
			size = kb.nextInt();
			
			if(sum != 0 && size == 0){
				
				System.out.println("Sums of " + sum + ":");
				System.out.print("NONE");
				continue;
			}
			
			
			obj = new SumItUp(sum, size);
			
			for(int i=0;i<size;i++){
				val = kb.nextInt();
				obj.addValToArr(i, val);
			}
			
			obj.calculateSum();
			obj.printSet();
			
		}while(size != 0 && sum != 0);
		
		kb.close();
	}
}