从n个数中找到和为m的数

2019独角兽企业重金招聘Python工程师标准>>>

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;

/*
 * Find the nums which sum is M
 */
public class FindMInN {
	public static void main(String args[]) {
		int arr[] = {1,2,4,7,11,15};
		List<Integer> li = new ArrayList<Integer>();
		li.add(1);
		li.add(2);
		li.add(4);
		li.add(7);
		li.add(11);
		li.add(15);
		//int arr[] = { 1, 2 ,2,2 };
		Stack<Integer> stack = new Stack<Integer>();
		findMInN(li, 2, 15, stack);
//		findMInN(arr, 15, 0, stack);
	}

//	public static void findMInN(int arr[], int m, int k, Stack<Integer> stack) {
//		if (k == arr.length) {
//			return;
//		}
//
//		for (int i = k; i < arr.length; i++) {
//			int remained = m - arr[i];
//			stack.add(arr[i]);
//			if (remained > 0) {
//				findMInN(arr, remained, k + 1, stack);
//			} else if(remained == 0){
//				Iterator itr = stack.iterator();
//				while (itr.hasNext()) {
//					System.out.println(itr.next());
//				}
//				System.out.println("Find the combination!");
//			}
//			stack.pop();
//		}
//
//	}
	
	public static void findMInN(List<Integer> li, int m, int remained, Stack<Integer> stack){
		
		if(m == 1 && li.contains(remained)){
			Iterator itr = stack.iterator();
			while (itr.hasNext()) {
				System.out.println(itr.next());
			}
			System.out.println("Remained " + remained);
			System.out.println("Find the combination!");
			return;
		} else if(m == 1 && !li.contains(remained)) {
			System.out.println("Not find element!");
			return;
		} 
		
		for(int i = 0; i < li.size(); i++){
			List<Integer> remainedList = new ArrayList<Integer>();
			for(int j = 0; j < li.size(); j++){
				if(j != i){
					remainedList.add(li.get(j));
				}
			}
			stack.add(li.get(i));
			findMInN(remainedList, m - 1, remained - li.get(i), stack);
			stack.pop();
		}
	}
}

转载于:https://my.oschina.net/u/138995/blog/308568