查找包含特定值的所有组合，其中所有值在数组中彼此相邻

Question

我有一个包含所有唯一值的可变长度数组，我需要找到索引彼此相邻且始终包含指定值的所有值组合。每个结果组合中值的顺序无关紧要（但我在我的示例中按顺序排列它们以更好地说明）。

例如：[5, 4, 2, 0, 1, 3]

如果选择的特定值为 0，我们将得到以下 12 种组合：
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

如果选择的特定值是 3，我们最终会得到以下 6 种组合：
3
1, 3
0, 1, 3
2, 0, 1, 3
4, 2, 0, 1, 3
5, 4, 2, 0, 1, 3

任何编程语言的答案都可以。

编辑：我认为这可以通过查找所有数字的所有组合然后缩小该列表以确保每个组合都满足要求来强制执行……这不理想但应该有效。

Answer 1

这个问题可以使用以下算法以 O(n^3) 的时间复杂度解决：

Step-1:找到目标元素的索引。

Step-2:遍历目标的索引到最右边的索引。我们将此迭代器称为 idx.

Step-3: 然后从目标索引开始迭代到最左边的索引。我们将此索引称为 i.

Step-4:打印索引idx和i之间的所有元素。

按照上述步骤将打印所有组合。

上述算法的代码是使用下面的python实现的。

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)

查找包含特定值的所有组合，其中所有值在数组中彼此相邻

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

algorithm

combinations