Google – All Numbers from Prime List

Google – All Numbers from Prime List
给一个包含distinct prime numbers 的数组，求所有能用这些prime numbers组成的数。
Follow up: 如果数组不是distinct, 有重复怎么办。
[Solution]
类似于subset i & ii, 每个subset的乘积，就是一个能组成的数。

  public List<Integer> fromPrimeNumber(int[] primes) {

    List<Integer> result = new ArrayList<>();

 

    Arrays.sort(primes);

    backtracking(primes, 0, result, 1, new HashSet<>());

    return result;

  }

 

  private void backtracking(int[] primes, int pos, List<Integer> result, int curr, Set<Integer> set) {

    result.add(curr);

    if (pos == primes.length) {

      return;

    }

 

    int i = pos;

    while (i < primes.length) {

      curr *= primes[i];

      backtracking(primes, i + 1, result, curr, set);

      curr /= primes[i];

 

      while (i + 1 < primes.length && primes[i] == primes[i + 1]) {

        i++;

      }

      i++;

    }

  }

Read full article from Google – All Numbers from Prime List