-4

Is it possible to write a subset sum algorithm with just for loops? I would assume the run time would be O(2^n)

Richard Samuel
  • 11
  • o(2^(n/2)) link at https://en.wikipedia.org/wiki/Subset_sum_problem – older coder Jan 23 '18 at 17:04
  • If you mean "just" for loops as in without recursion, then yes, and the same is also true for every other recursive algorithm ever. Although that doesn't necessarily change what high-level steps the algorithm takes, just what the code looks like. – Bernhard Barker Jan 23 '18 at 17:20
  • Don't tag java or any other language if your question is not related to that. Also try to be more specific about your question. – HariUserX Jan 23 '18 at 17:22
  • @Dukeling If we're talking about classic `for` loops with a definite upper bound, that's not true in general. Only primitive recursive functions can be computed with them, so for example the Ackermann function can't. But since the subset-sum problem has at most `2^n` solution candidates, it is primitive recursive. – biziclop Jan 23 '18 at 17:50
  • @biziclop I'm not talking about a specific subset of for loops. – Bernhard Barker Jan 23 '18 at 18:36

2 Answers2

0

Refer to wiki

you can actually solve it in O(n x sum) time complexity using dynamic programming. But it also requires space complexity of O(n x sum) to store the boolean table that is filled in bottom up manner. You can just google the solution for it.

By only for loop I think you meant, without using dynamic approach. Then we have exponential complexity like you said.

HariUserX
  • 1,341
  • 1
  • 9
  • 17
0
public static ArrayList<ArrayList<Integer>> powerSet(List<Integer> intList) {
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    result.add(new ArrayList<Integer>());

    for (int i : intList) {
        ArrayList<ArrayList<Integer>> temp = new ArrayList<ArrayList<Integer>>();

        for (ArrayList<Integer> innerList : result) {
            innerList = new ArrayList<Integer>(innerList);
            innerList.add(i);
            temp.add(innerList);
        }
        result.addAll(temp);
    }

    return result;
}
public static List<Integer> subsetSum(int[] group){
    List<Integer> mySet = new ArrayList<>();
    for(int i=0;i<group.length;i++){
        mySet.add(group[i]);
    }
    ArrayList<ArrayList<Integer>> setArry=powerSet(mySet);
    for (int i=0;i<setArry.size();i++){
        ArrayList<Integer> oneSet= setArry.get(i);
        if(oneSet.size()>0){
        int sum =0;
        for (int t=0;t<oneSet.size();t++){
            sum+=oneSet.get(t);
        }
        if(sum==0){
            return oneSet;
        }
        }
    }
    return null;
}
public static void main(String[] args){
  List<Integer> res = subsetSum(group);
    if(res!=null){
      for (Integer i:res) {
        System.out.print(i+" ");
      }
    }else {
        System.out.println("false");
    }
}

powerSet credit Calculating all of the subsets of a set of numbers

Sarel Foyerlicht
  • 907
  • 6
  • 11