alex.climov
BAN USERimport b.k.P;
import java.util.*;
public class Main {
public static void main(String[] args) {
int[]n = new int []{1,2,3,5,6,11};
boolean[] used =new boolean[n.length];
int r = solve(n.length,n,used);
}
static int solve(int remain, int[] nums, boolean[] used){
int res = remain;
if(remain<3){
return remain;
}
for(int i=0;i<nums.length;i++){
if(!used[i]){
//try it as sum-> get all subsets
used[i]=true;
remain--;
List<List<Integer>> subsets = new ArrayList<List<Integer>>();
getsets(nums[i],nums,used,new ArrayList(),subsets,0);
if(subsets.size()>0){
for(List<Integer> l :subsets){
for(Integer j:l){
used[j]=true;
remain--;
}
res = Math.min(solve(remain,nums,used),res);
for(Integer j:l){
used[j]=false;
remain++;
}
}
}
used[i]=false;
remain++;
}
}
return res;
}
static void getsets(int target,int[]nums,boolean[]used,ArrayList<Integer> temp,List<List<Integer>> res,int idx){
if(target==0){
res.add(new ArrayList<Integer>(temp));
return;
}
for(int i=idx;i<nums.length;i++){
if(used[i]||target-nums[i]<0){continue;}
used[i]=true;
target-=nums[i];
temp.add(i);
getsets(target,nums,used,temp,res,i+1);
temp.remove(temp.get(temp.size()-1));
used[i]=false;
target+=nums[i];
}
}
}
- alex.climov September 10, 2017