the least adding numbers--algorithm -

i came across problem online.

given integer:n , array int arr[], have add elements array can generate 1 n using (add) element in array.

please keep in mind can use each element in array once when generating x (1<=x<=n). return number of least adding numbers.

for example:  n=6, arr = [1, 3]   1 in arr.   add 2 arr.   3 in arr   4 = 1 + 3   5 = 2 + 3   6 = 1 + 2 + 3   return 1 since need add 1 element 2. 

can give hints?

n can made adding subset of 1 n - 1 numbers except n = 2 , n = 1. so, number x can must made when previous 1 x - 1 consecutive elements in array. example -

    arr[] = {1, 2, 5}, n = 9     ans := 0     1 present.     2 present.     3 absent. prior 1 (3 - 1) elements present. 3 added in array. 3 built using existed elements, answer won't increase.     same rule 4 , 5      so, ans 0      arr[] = {3, 4}, n >= 2      ans = 2      arr[] = {1, 3}, n >= 2      ans = 1 

so, seems that, if 1 , 2 not present in array, have add element regardless of previous elements in array or not. later numbers can made using previous elements. , when trying making number x (> 2), found previous 1 x - 1 elements in array. x can made.

so, need check if 1 , 2 present or not. answer of problem won't bigger 2

constraint 2

in above algorithm, assume, when new element x not present in array can made using existed elements of array, answer won't increase x added in array used next numbers building. if x can't added in array?

then, turn subset sum problem. every missing number have check if number can made using subset of elements in array. typical o(n^2) dynamic programming algorithm.

int subsetsum(vector<int>& arr, int n) {     // value of subset[i][j] true if there subset of set[0..j-1]     //  sum equal     bool subset[n + 1][arr.size() + 1];      // if sum 0, answer true     (int = 0; <= arr.size(); i++)       subset[0][i] = true;      // if sum not 0 , set empty, answer false     (int = 1; <= n; i++)       subset[i][0] = false;       // fill subset table in botton manner      (int = 1; <= n; i++)      {        (int j = 1; j <= arr.size(); j++)        {          subset[i][j] = subset[i][j - 1];          if (i >= set[j - 1])            subset[i][j] = subset[i][j] || subset[i - set[j - 1]][j - 1];        }      }       unordered_map<int, bool> exist;      for(int = 0; < arr.size(); ++i) {          exist[arr[i]] = true;      }       int ans = 0;      for(int = 1; <= n; ++i) {           if(!exist[i] or !subset[i][arr.size()]) {               ans++;           }      }       return ans; }