CODEWITHSUNDEEP
algorithmcombinations
NitrusAphalion
NitrusAphalion

Reputation: 165

Find all combinations that include a specific value where all values are next to each other in array

I have an array of variable length containing all unique values and I need to find all combinations of values whose indices are next to each other and always include a specified value. The order of values in each resulting combination doesn't matter (However I kept them in order in my example to better illustrate).

As an example: [5, 4, 2, 0, 1, 3]

If the specific value chosen is 0, we would end up with the following 12 combinations:
0
0, 1
2, 0
0, 1, 3
2, 0, 1
4, 2, 0
2, 0, 1, 3
4, 2, 0, 1
5, 4, 2, 0
4, 2, 0, 1, 3
5, 4, 2, 0, 1
5, 4, 2, 0, 1, 3

If the specific value chosen is 3, we would end up with the following 6 combinations:
3
1, 3
0, 1, 3
2, 0, 1, 3
4, 2, 0, 1, 3
5, 4, 2, 0, 1, 3

Answers in any programming language will work.

EDIT: I believe this can be brute forced by finding all combinations of all numbers and then narrowing that list to make sure each combination meets the requirements...its not ideal but should work.

Upvotes: 0

Views: 278

Answers (1)

Yash Shah
Yash Shah

Reputation: 1654

This problem could be solved in O(n^3) time-complexity using the following algorithm:

Step-1: Find the index of the target element.

Step-2: Iterate through an index of the target to the rightmost index. Let's call this iterator as idx.

Step-3: Then iterate from the target index to the leftmost index. Let's call this index as i.

Step-4: Print all the elements between the indices idx and i.

Following the above steps will print all the combinations.

The code for the above algorithm is implemented using python below.

def solution(array,target):
    
    index = -1
    for idx,element in enumerate(array):
        if(element == target):
            index = idx
            
    n = len(array)
    
    for idx in range(n-1,index-1,-1):
        for i in range(index,-1,-1):
            for j in range(i,idx+1):
                print(array[j],end = ",")
            print()
        

arr = [5, 4, 2, 0, 1, 3]
target = 0
solution(arr,target)

Upvotes: 1

Related Questions