leetcode解題のCombination Sum III java版(組合せ求和III)

216. Combination Sum III
Find all possible combinations of k numbers that add up to a numbern, 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]]

1つの数字は1回しか使用できません.昇順に並べて、

public List> combinationSum3(int k, int n) {
		List> res = new ArrayList>();
		List tmp = new ArrayList<>();
		//       1  
		dfsCore(res, 1, 0, tmp, n, k);
		return res;
	}

	private void dfsCore(List> res, int curIdx, int sum, List tmp, int n, int k) {

		if (sum > n)
			return;
		if (k < 0)
			return;
		if (sum == n && k == 0) {
			res.add(new ArrayList(tmp));
			return;
		}
		// For     curIdx  ，          
		for (int i = curIdx; i < 10; i++) {
			//   
			if (n < sum)
				return;
			sum += i;
			tmp.add(i);
			//   i+1
			//    i++       i+1   
			i++;
			dfsCore(res, i, sum, tmp, n, k - 1);
			//   
			i--;
			tmp.remove(tmp.size() - 1);
			sum -= i;
		}

	}

377. Combination Sum IV
Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.
Example:

nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.

Follow up: What if negative numbers are allowed in the given array? How does it change the problem? What limitation we need to add to the question to allow negative numbers?
最初はDFSでやろうと思っていましたが、このようにして得られた答えは、それぞれの数字の配列が無秩序であること、つまり1、3、3、1という答えが1つの答えであり、それから数字を保存して、1つの答えを得たときにこれらの数字をもう一度合計して配列した個数を求めたいという問題がありました.このような方法には、総配列個数を求めるときに例えば2、1,1の3つを合わせると4になり、合計の配列個数は(3!/2!)、しかし、数字の個数が多い場合、階乗が大きすぎて計算できない.そして動的計画で行うことができることもリュックサックの問題であると考え,[1,target]間の位置ごとにどれだけの配列方式があるかを求め,問題をサブ問題に分化する.状態遷移方程式は、dp[i]=sum(dp[i−nums[j]),(i−nums[j]>0)とすることができる.
ここでdp[i]は、数字iを生成するすべての可能な配列方式の個数を表す.負数が許される場合は、数ごとに使える回数を制限しなければなりません.そうしないと、1,-1,target=1のような無限大な配列が得られます.
タイムアウトバージョン

public int combinationSum4(int[] nums, int target) {
		Arrays.sort(nums);
		dfsCore(0, 0, nums, target);
		return count;
	}
	int count = 0;
	private void dfsCore(int curIdx, int sum, int[] nums, int target) {
		if (sum > target)
			return;
		if (sum == target)
			++count;
		// i 0  ，     ，            
		for (int i = 0; i < nums.length; i++) {
			//             
			if (sum > target)
				return;
			sum += nums[i];
			//    i+1 ，    
			dfsCore(i, sum, nums, target);
			sum -= nums[i];
		}

	}

public int combinationSum4(int[] nums, int target) {
		int[] dp = new int[target + 1];
		dp[0] = 1;
		//           
		for (int i = 1; i <= target; i++) {
			for (int j = 0; j < nums.length; j++) {
				//   nums  i         
				if (i >= nums[j]) {
					//        ，           
					dp[i] += dp[i - nums[j]];
				}
			}
		}
		return dp[target];
	}

更新:
DFS+記憶化探索アルゴリズム,mapを用いて不要な計算を除去

//DFS+     
public class Solution {
	Map map = new HashMap<>();

	public int combinationSum4(int[] nums, int target) {
		int count = 0;
		if (nums == null || nums.length == 0 || target < 0)
			return 0;
		if (target == 0)
			return 1;
		if (map.containsKey(target))
			return map.get(target);
		for (int num : nums) {
			count += combinationSum4(nums, target - num);
		}
		map.put(target, count);
		return count;
	}
}

参照先:
39. Combination Sum
40. Combination Sum II
78. Subsets
90. Subsets II