I have to find all the combinations in an array a[] with indices i,j,k such that i<j<k and have to perform one operation for every combination for example in an array int a[] = {12,1,34,32} the combination are {12,1,34},{12,1,32},{12,34,32}.{1,34,32}

I have tried recursive way and storing all the combinations in a set so that if I visit the same combination again I will return from there only by checking it from the set

my code is this but i am getting TLE for large cases can anyone please provide me the most efficient way for this

 static Set<String> set = new HashSet<>();
 static int sum = 0;

    static void solve(int i,int j,int k,int[] a){
        if(i>=j || j>=k ||k>=a.length){
            return;
        }
        
        //combination
        String pre = String.valueOf(i) String.valueOf(j) String.valueOf(k);
        if(set.contains(pre)){
            return;
        }

        //operation to perform for every combination
        int v = (a[i] | a[j] | a[k]) ^ (a[i] ^ a[j] ^ a[k]);
        sum = sum v;

        solve(i,j,k 1,a);
        solve(i,j 1,k,a);
        solve(i 1,j,k,a);
    }

CodePudding user response：

For three indices it is simpler to make three loops. Also I added precalculation of two binary operations and removed set check for simplicity.

static int solve(int[] a){
    int leng = a.length;
    int sum = 0;
    for (i=0; i < leng-2; i  )   {
       for (j=i 1; j < leng - 1; j  )   {
           int ijor = a[i] | a[j];
           int ijxor = a[i] ^ a[j];
           for (k=j 1; k < leng; k  )   {
              //operation to perform for every combination
             sum = sum   (ijor | a[k]) ^ (ijxor ^ a[k]);
           }
        }
     }
     return sum; 
}

CodePudding user response：

I see you are using java, however, I'm able to provide an answer with python but I'm sure that there are equivalent operations in java too:

from itertools import combinations
def combs_tri(X):
    lenght=len(X)
    num_of_zeros=lenght-3
    def factorial(n):
        m=1
        for x in range(1,n 1):
            m=m*x
        return m
    def num_of_comb(n,z):
        return int(factorial(lenght)/(factorial(z)*factorial(lenght-z)))
    count=num_of_comb(lenght,3)
    def create_boolean_array(num_of_zeros,count,lenght):
        Arr=np.zeros((count,lenght))
        combs=list(combinations(range(lenght), 3))
        for i,comb in enumerate(combs):
            Arr[i,comb]=1
        return Arr
    repeated_list=np.repeat([X],count,axis=0)
    bool_mask=create_boolean_array(num_of_zeros,count,lenght)
    return repeated_list[bool_mask.astype(bool)].reshape((int(count)),3)

In most cases array operations are much faster than for loops.