Prime Combination

题目地址：
http://www.1point3acres.com/bbs/thread-283570-1-1.html

题目：
给出一组质数， 求出所有可以得到的乘积，一个乘积只能用一次相同的质数。 比如给出{2,3,5} 要返回{2,3,5,6,10,15,30}. (不会有12, 18 因为 6 = 2 * 3, 所以不能在乘以2, 3)。

解题思路：
这道题就是用dfs来解决。

代码：

public class PrimeCombination {

    public List<Integer> combine(int[] primes){
        List<Integer> rst = new ArrayList<>();
        List<List<Integer>> helper = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        if(primes == null || primes.length == 0){
            return rst;
        }
        dfs(primes, helper, list, 0);
        for(int i = 0; i <= helper.size() - 1; i++){
            List<Integer> temp = helper.get(i);
            int product = 1;
            for(int j = 0; j <= temp.size() - 1; j++){
                product *= temp.get(j);
            }
            rst.add(product);
        }
        return rst;
    }

    private void dfs(int[] primes, List<List<Integer>> helper, List<Integer> list, int pos) {
        if(list.size() != 0){
            helper.add(new ArrayList<>(list));
        }
        if(pos == primes.length){
            return;
        }
        for(int i = pos; i <= primes.length - 1; i++){
            list.add(primes[i]);
            dfs(primes, helper, list, i + 1);
            list.remove(list.size() - 1);
        }
    }

    public static void main(String[] args){
        PrimeCombination primeCombination = new PrimeCombination();
        int[] input = new int[]{2, 3, 5};
        List<Integer> rst = primeCombination.combine(input);
        System.out.println(rst);
    }

}