Как получить все возможные варианты удаления элементов из отсортированного списка?

Question

Например есть отсортированный список: [1, 2, 3, 4] Каким образом можно получить возможные варианты с удалением элементов? Чтобы вначале удалялся один элемент, потом два, потом три и т.д. Как я понимаю необходимо использовать рекурсию. В результате должно получиться

[2, 3, 4]
[1, 3, 4]
[1, 2, 4]
[1, 2, 3]
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]
[1]
[2]
[3]
[4]

Answer 1

По сути каждый элемент может участвовать или не участвовать в результате.

Отсюда можно придумать алгоритм. Я на C# его напишу, на Java там 1-1 почти будет.

public void AllCases(int[] data, int ind, List<int> current, List<List<int>> ret)
{
    if (ind >= data.Length)
    {
        ret.Add(new List<int>(current));
        return;
    }

    current.Add(data[ind]);
    AllCases(data, ind + 1, current, ret); // участвует

    current.RemoveAt(current.Count - 1);
    AllCases(data, ind + 1, current, ret); // не участвует
}

Проверка элементарная

var ret = new List<List<int>>();
AllCases(new[] { 1, 2, 3, 4 }, 0, new List<int>(), ret);

foreach (var list in ret)
    Console.WriteLine(string.Join(", ", list));

Вывод

1, 2, 3, 4
1, 2, 3
1, 2, 4
1, 2
1, 3, 4
1, 3
1, 4
1
2, 3, 4
2, 3
2, 4
2
3, 4
3
4

БЛОГ НА HUSL

Как получить все возможные варианты удаления элементов из отсортированного списка?

Ответы (1 шт):