Для заданного массива цифр 0-9 и целого числа n найдите все целые числа, которые можно сформировать из входного массива с числом цифр = n.

Question

Обратите внимание, что это не дубликат этого , а скорее его подзадача.

Вот проблема:

Вам дан массив цифр 0-9 и целое число n. Массив может содержать дубликаты любой заданной цифры. Найдите все целые числа, которые могут быть образованы путем соединения цифр из входного массива и имеют n цифр. Цифры из входного массива могут повторяться в элементе на выходе.

Например, если заданы как входные данные [2, 5] и n = 3, то следующим выводом должно быть:

[222, 225, 252, 255, 522, 525, 552, 555]

Обратите внимание, что именно это вычисляет Python itertools.product . Их алгоритм указан по этой ссылке - я не могу определить его сложность во время выполнения, но думаю, что он оптимален. Какова сложность во время выполнения этого решения?

Answer 1

vector<string> result;

// storing the concatenation of digits as a string as it is to operate on, we can convert the concatenated string to int at the end.

FormDigits(vector<int> input, int index, int n, string ndigits) {

 // if the ndigits size has reached n
 // Check whether that is already present in the result as we have repeating digits
 if(ndigits.size() == n && result.find(ndigits) != result.end()) { 
     result.push(ndigits);
 } 

  // if ndigits size hasnt yet reached run a loop and add next digit 
 else {
    for(int i=index; i<input.size(); i++) {
        FormDigits(input,i,n,digit+to_string(arr[i]));
    }
 }
}

Вышеуказанная функция должна вызываться из main как

FormDigits(InputArray, 0, n, "");

Вектор результата - это конечный результат.