Array Processing logic correction

Question

I have an array [1,2,4,5,1,7,8,9,2,3]

and i would like it to generate all subset which sum of values are less than 10

current result [[1,2,4],[5,1],[7],[8],[9],[2,3]]

expected result [[4,5,1],[9,1],[8,2],[3,7],[1,2]]

that is what i did

var a = [1,2,4,5,1,7,8,9,2,3], tempArr = []; tempSum = 0, result = [];
for (var i = 0;i< a.length; i += 1 ) {
  tempSum+=a[i];
  tempArr.push(a[i]);
  if((tempSum+a[i+1])>10) {
     result.push(tempArr);
     tempSum = 0;
     tempArr = [];
  } else if (i == a.length-1 && tempArr.length > 0) { // if array is [1,2,3]
    result.push(tempArr);
  }
}

but it gives me [[1,2,4],[5,1],[7],[8],[9],[2,3]] and it has 6 subset, but i expect to get [[4,5,1],[9,1],[8,2],[3,7],[1,2]] which has 5 subset.

your question speaks about *"by the sum of values less than 10 "*, but you mean in the expected result exactly 10 or groups of less than 10. is another rule, for example to keep the item count in a single array low, like [7, 3] instead of [7, 2, 1]? — Nina Scholz, Jun 09 '17 at 11:41
You have only two 1s to start with but use three 1s to produce the result. How so.? — Redu, Jun 10 '17 at 06:50

shivam · Accepted Answer · 2017-06-12T07:10:11.133

1

Below logic is in JavaScript :-

var limit = 10;
var  arr = [1,2,4,5,1,7,8,9,2,3];
arr.sort();
var ans = new Array ( );
while(arr.length >0){
    var ts = arr[arr.length-1];
    arr.splice(arr.length-1 , 1);   
    var ta= new Array ( );
    ta.push(ts);
    var x = arr.length-1;
    while(x>=0){    
        if(ts + arr[x] <= limit){       
            ts = ts + arr[x];           
            ta.push(arr[x]);        
            arr.splice(x , 1);
        }
        x= x-1;
    }
        ans.push(JSON.stringify(ta));   
}
alert(ans);

It is Giving Output as required .

[9,1],[8,2],[7,3],[5,4,1],[2]

edited Jun 12 '17 at 07:10

answered Apr 23 '17 at 09:30

shivam

489
2
8
22

i added a const a = a[i+1] ? a[i+1] : 0; – Niyaz Jun 06 '17 at 11:22
please let us know which language you are using . – shivam Jun 08 '17 at 13:16
i am using javascipt – Niyaz Jun 08 '17 at 17:37
There are two mistake in asked question .please rectify it 1. generate all subset which sum of values are less than 10 but output contain [(9,1), (8,2), (7,3), (4,5,1)] 2.there are 2 times "1" in input but output contain "1" 3 times – shivam Jun 12 '17 at 07:13

fingerpich · Answer 2 · 2017-06-12T08:23:04.983

I have removed duplicates then added maxSum parameter to combine function to generate all subset which have those conditions and then sorted subsets by sum of the values and sliced them.

You could change parameters to fit it for your problem.

var arr = [1,2,4,5,1,7,8,9,2,3]
MAX_SUM = 10,
MIN_SUBSET_LEN = 2,
RESULT_LEN = 5;

//remove duplicates
var uniqeSet = arr.filter(function(value, index){ 
  return this.indexOf(value) == index 
},arr);

// a function to get all subset which 
// their length are greater than minLength and 
// sum of values are little than maxSum
var combine = function(sourceArr, minLength, maxSum) {
    var fn = function(n, src, got, all, sum) {
        if(sum <= maxSum){
          if (n == 0) {
            if (got.length > 0) {
                all.push({arr:got,sum:sum});
            }
            return;
          }
          for (var j = 0; j < src.length; j++) {
            var tempSum = sum
            fn(n - 1, src.slice(j + 1), got.concat([src[j]]), all, sum + src[j]);
          }
        }
        return;
    }
    
    var all = [];
    for (var i = minLength; i < sourceArr.length; i++) {
        fn(i, sourceArr, [], all, 0);
    }
    return all;
}


var result = combine(uniqeSet, MIN_SUBSET_LEN, MAX_SUM);

var sortedSliced = result.sort(function(a1, a2){
  return a2.sum - a1.sum;
}).slice(0, RESULT_LEN).map(function(m){return m.arr;});

console.log(JSON.stringify(sortedSliced));

Array Processing logic correction

2 Answers2