Что при возврате назад решает, должен ли следующий рекурсивный вызов последовательно перемещаться к следующей позиции/пе ⇐ JAVA

[Anonymous]

В некоторых задачах, таких как перестановки, мы заполняем позиции одну за другой, а в других, таких как подмножества или разбиение, мы продвигаемся вперед на основе уже выбранных элементов. Почему эти проблемы решаются по-разному после каждого шага?
Для возврата всех возможных перестановок:

Код: Выделить всё

class Solution {
public List permute( int[] nums ) {
List ans = new ArrayList();
set( 0, nums, ans );
return ans;
}

public void set( int ind, int nums[],
List ans ) {
if( ind == nums.length ) {
// logic to return ans
return;
}

for( int i = ind; i < nums.length; i++ ) {
swap( i, ind, nums );
set( ind + 1, nums, ans ); // Why don’t we use i + 1 here?
swap( i, ind, nums );
}
}

public void swap( int i, int j, int arr[] ) {
// swap logic
}
}

Для возврата палиндромного разделения строки:

Код: Выделить всё

class Solution {
public List partition( String s ) {
List ans = new ArrayList();
List ds = new ArrayList();
partition( 0, ans, ds, s );
return ans;
}

public void partition( int ind, List ans,
List ds, String s ) {
if( ind == s.length() ) {
// logic to return ans
return;
}
for( int i = ind; i < s.length(); i++ ) {
if( ispalindrome( s, ind, i )) {
ds.add( s.substring( ind, i + 1 ));
partition( i + 1, ans, ds, s ); // here we did not use ind+1, why?
ds.remove( ds.size() - 1 );
}
}
}
}

Теперь вы можете объяснить, почему i+1 используется для вызова рекурсии внутри цикла for при перестановках. И почему ind+1 используется для вызова рекурсии внутри цикла for при секционировании палиндромов.