正准备睡觉,瞬间有了思路。。。
先来个js版本的---我是前端(:
function forFn($i,$max,$sum,$sum_end,$loop_num,$loop_index,$indexArr){
if($loop_index==$loop_num){
if($sum==$sum_end){
console.log('///$sum:'+$sum+'/$sum_end:'+$sum_end+'/$indexArr:'+$indexArr+'/$loop_index:'+$loop_index);
}
return false;
}else{
for(var $ii=$i;$ii<=$max;$ii++){
$indexArr[$loop_index]=$ii;
if($indexArr[$loop_index]>($max-$loop_num+1+$loop_index)){
break;
}
$sum=eval($indexArr.join("+"));
console.log('$sum:'+$sum+'/$sum_end:'+$sum_end+'/$loop_index:'+$loop_index+'/$ii:'+$ii+'/$indexArr:'+$indexArr);
forFn($ii+1,$max,$sum,$sum_end,$loop_num,$loop_index+1,$indexArr);
}
}
};
function addFn($min,$max,$sum,$sum_end,$loop_num,$loop_index,$indexArr){
for(var $i=$min;$i<=$max-$loop_num+1;$i++){
var $loop_index=0;
$indexArr[$loop_index]=$i;
forFn($i+1,$max,$sum,$sum_end,$loop_num,$loop_index+1,$indexArr)
}
}
addFn(0,999,0,12865,30,0,[])
php:
function forFn($i,$max,$sum,$sum_end,$loop_num,$loop_index,$indexArr){
if($loop_index==$loop_num){
if($sum==$sum_end){
echo('///$sum:'.$sum.'/$sum_end:'.$sum_end.'/$indexArr:'.$indexArr);
print_r($indexArr);
};
return false;
}else{
for($ii=$i;$ii<$max;$ii++){
$indexArr[$loop_index]=$ii;
if($indexArr[$loop_index]>($max-$loop_num+1+$loop_index)){
break;
}
$sum=array_sum($indexArr);
forFn($ii+1,$max,$sum,$sum_end,$loop_num,$loop_index+1,$indexArr);
}
}
};
function addFn($min,$max,$sum,$sum_end,$loop_num,$loop_index,$indexArr){
for($i=$min;$i<($max-$loop_num+1);$i++){
$loop_index=0;
$indexArr[$loop_index]=$i;
forFn($i+1,$max,$sum,$sum_end,$loop_num,$loop_index+1,$indexArr)
}
}
addFn(0,999,0,12865,30,0,[])
刚刚用node跑了一下,没跑完(复杂度太大),也不知道对不对,谁跑完结果告诉我一下(:
可以睡觉去了。。。
用测试数据0,1,2,3跑了一下
[0,1,2,3]取3个数字,和为6;
addFn(0,3,0,6,3,0,[])
dp, 只用一维数组节省内存, 但是题目复杂度太大... 不玩了.
public Set<List<Integer>> compute(int N, int SUM, int MAX_KEY) {
Set<List<Integer>>[] pre = null;
Set<List<Integer>>[] cur = new Set[SUM + 1];
// one elem
for (int i = 0; i <= MAX_KEY; i++) {
cur[i] = new HashSet<>();
cur[i].add(Collections.singletonList(i));
}
for (int i = 2; i <= N; i++) {
pre = cur;
cur = new Set[SUM + 1];
for (int j = 0; j <= SUM; j++)
for (int k = 0; k <= MAX_KEY; k++)
if (j - k >= 0 && pre[j - k] != null) {
if (cur[j] == null)
cur[j] = new HashSet<>();
for (List<Integer> l: pre[j - k]) {
List<Integer> tmp = new ArrayList<>(l);
tmp.add(k);
Collections.sort(tmp);
cur[j].add(tmp);
}
}
}
return cur[SUM];
}
@Test
public void test(){
compute(30, 12865, 999);
}
二维数组, 太费内存
private Set<List<Integer>>[][] dp = null;
private Set<List<Integer>> res = null;
public Set<List<Integer>> compute(int N, int SUM, int MAX_KEY) {
dp = new Set[N + 1][SUM + 1];
for (int i = 0; i <= MAX_KEY; i++) {
dp[1][i] = new HashSet<>();
dp[1][i].add(Collections.singletonList(i));
}
for (int i = 2; i <= N; i++)
for (int j = 0; j <= SUM; j++)
for (int k = 0; k <= MAX_KEY; k++)
if (j - k >= 0 && dp[i - 1][j - k] != null) {
if (dp[i][j] == null)
dp[i][j] = new HashSet<>();
for (List<Integer> l: dp[i - 1][j - k]) {
List<Integer> tmp = new ArrayList<>(l);
tmp.add(k);
dp[i][j].add(tmp);
}
}
return dp[N][SUM];
}
Java代码. 用了一些优化提高效率, 但复杂度还是太高. 权当参考吧.
private Set<Long> failedSet = null;
private Set<List<Integer>> res = null;
public Set<List<Integer>> compute() {
failedSet = new HashSet<>();
res = new HashSet<>();
computeInt(30, 12865, 999, new int[30]);
return res;
}
private boolean computeInt(int count, int sum, int max, int[] arr) {
if (count == 0 || sum < 0) {
if (sum == 0){
List<Integer> tmp = Arrays.stream(arr).sorted().boxed()
.collect(Collectors.toList());
res.add(tmp);
}
return sum == 0;
}
long key = (long)count * Integer.MAX_VALUE + sum;
if (failedSet.contains(key))
return false;
boolean found = false;
for (int i = 0; i <= max; i++) {
arr[count - 1] = i;
if (computeInt(count - 1, sum - i, Math.min(max, i), arr))
found = true;
}
if (!found)
failedSet.add(key);
return found;
}