p216

LeetCode p216 Combination Sum III 题解

1.题目：

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
Example 1:
Input: k = 3, n = 7
Output:
[[1,2,4]]
Example 2:
Input: k = 3, n = 9
Output:
[[1,2,6], [1,3,5], [2,3,4]]

题意：

输入k,n。希望可以由K个数，相加得n.输出所有可能。（只能含有1到9之间的数）。

2.解题思路:

递归。注意数字不能重复出现，以及边界条件。

3.代码

---

[title] [] [url] [link text]

 
public class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {

		List<List<Integer>> ansList = new ArrayList<List<Integer>>();
		List<Integer> list = new ArrayList<Integer>();
		dp(k, n, list, ansList, 1);
		return ansList;
	}

	public void dp(int k, int n, List<Integer> list,
			List<List<Integer>> ansList, int b) {

		if (k == 1) {
			if (n > 0 && n < 10) {
				list.add(n);
				List<Integer> aList=new ArrayList<Integer>(list);//新对象
				ansList.add(aList);
				// System.out.println(list);
				list.remove(list.size() - 1);
			}
		}

		for (int i = b; i < 10; i++) {
			if (n - i > i)

			{
				list.add(i);
				dp(k - 1, n - i, list, ansList, i + 1);
				list.remove(list.size() - 1);
			} else {
				return;
			}
		}
		return;

	}
}

---

4.一些总结：