Dada una array nums [ ] y un objetivo entero. Encuentre si existe una combinación de números enteros en nums [ ] tal que su suma sea igual al objetivo y ninguno de esos elementos sea adyacente en la array original.
Ejemplo :
Entrada : nums[] = [1, 2, 2, 3], destino = 4
Salida : verdadero
Explicación : podemos elegir [1, 3] ya que no son adyacentes y suman 4Entrada : nums[ ] = [1, 3, 1], destino = 4
Salida: falso
Explicación : no podemos elegir [1, 3] o [3, 1] porque son adyacentes.
Enfoque : el problema se puede resolver utilizando la programación dinámica según los pasos a continuación:
- dp[i][j]: Cree una array dp 2-d que almacene si es posible lograr una suma de exactamente j después de considerar los primeros elementos i de la array.
- En un índice i dado y una suma j dada, puede haber dos casos:
- O podemos incluir el número actual, nums[i], o no lo hacemos.
- Si no incluimos el número actual, simplemente miramos hacia atrás a la fila anterior del dp.
- Si incluimos el número actual, tenemos que mirar hacia atrás dos filas en la array dp, porque no se pueden seleccionar elementos adyacentes.
- Entonces, una vez que seleccionamos el elemento i, podemos ignorar el elemento i-1 ya que no se puede tomar.
- Caso base:
- Inicialmente inicialice la tabla booleana dp con false.
- Luego, complete verdadero en la primera columna ya que la suma 0 siempre se puede lograr al no tomar ningún elemento.
- También llene dp[i][nums[i]] con valores verdaderos, lo que indica que podemos lograr una suma de nums[i] después de considerar los primeros i elementos de la array (lo cual es obvio simplemente tome el elemento en el índice i) .
- Estados de transición :
- Caso 1: dp[i][j] = dp[i – 1][j] || dp[i][j]
- verifique el valor en la fila anterior
- si es cierto, podemos hacer que la suma del subconjunto sea igual al objetivo tomando elementos hasta la última fila,
- Así que haz que dp[i][j] también sea verdadero
- Caso 2: dp[i][j] = dp[i – 2][j – nums[i]] || dp[i][j]
- verifique si agregamos el elemento actual nums[i] a la fila actual – 2 (ya que no es adyacente) tabla dp y hacemos que la suma sea igual al objetivo.
- Caso 1: dp[i][j] = dp[i – 1][j] || dp[i][j]
Ilustración:
Considere el ejemplo donde nums[ ] = [1, 2, 2, 3], target = 4
La tabla dp se vería como la siguiente (i representa nums[i] y j representa el objetivo)
i (números [i]) \ j (objetivo) 0 1 2 3 4 0 (números[0]=1) verdadero verdadero falso falso falso 1 (números[1]=2) verdadero verdadero verdadero falso falso 2 (números[2]=2) verdadero verdadero verdadero verdadero falso 3 (numeros[2]=3) verdadero verdadero verdadero verdadero verdadero
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement above approach
#include <bits/stdc++.h>
using namespace std;
bool subsetSumNonAdjacent(
vector<int>& nums, int target)
{
// size of the array
int n = nums.size();
// Boolean dp table fill with false
vector<vector<bool> > dp(
n, vector<bool>(target + 1, false));
// Base Case
// Initialize dp[i][0]= true
// as 0 can always be achieved
// by not taking anything
for (int i = 0; i < n; i++) {
dp[i][0] = true;
}
// Initialize dp[i][nums[i]]= true
// as nums[i] can always be achieved
// by taking only element
// at index i that is nums[i]
for (int i = 0; i < n; i++) {
dp[i][nums[i]] = true;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j <= target; j++) {
// check if we can take previous row
if (i - 1 >= 0) {
dp[i][j]
= dp[i - 1][j] || dp[i][j];
}
// check for row-2
if (i - 2 >= 0 && j >= nums[i]) {
dp[i][j]
= dp[i - 2][j - nums[i]]
|| dp[i][j];
}
}
}
return dp[n - 1][target];
}
// Driver code
int main()
{
vector<int> nums = { 1, 2, 2, 3 };
int target = 4;
cout << boolalpha
<< subsetSumNonAdjacent(nums, target);
return 0;
}
Java
// Java Program of the above approach.
import java.util.*;
class GFG {
static boolean subsetSumNonAdjacent(int[] nums, int target)
{
// size of the array
int n = nums.length;
// Boolean dp table fill with false
boolean[][] dp = new boolean[n][target + 1];
for (int i = 0; i < n; i++) {
for (int j = 0; j < target + 1; j++) {
dp[i][j] = false;
}
}
// Base Case
// Initialize dp[i][0]= true
// as 0 can always be achieved
// by not taking anything
for (int i = 0; i < n; i++) {
dp[i][0] = true;
}
// Initialize dp[i][nums[i]]= true
// as nums[i] can always be achieved
// by taking only element
// at index i that is nums[i]
for (int i = 0; i < n; i++) {
dp[i][nums[i]] = true;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j <= target; j++) {
// check if we can take previous row
if (i - 1 >= 0) {
dp[i][j] = dp[i - 1][j] || dp[i][j];
}
// check for row-2
if (i - 2 >= 0 && j >= nums[i]) {
dp[i][j] = dp[i - 2][j - nums[i]]
|| dp[i][ j];
}
}
}
return dp[n - 1][target];
}
// Driver Code
public static void main(String args[])
{
int[] nums = { 1, 2, 2, 3 };
int target = 4;
System.out.print(subsetSumNonAdjacent(nums, target));
}
}
// This code is contributed by code_hunt.
Python3
# Python program to implement above approach def subsetSumNonAdjacent(nums,target): # size of the array n = len(nums) # Boolean dp table fill with false dp = [[False]*(target+1)]*n # Base Case # Initialize dp[i][0]= true # as 0 can always be achieved # by not taking anything for i in range(n): dp[i][0] = True # Initialize dp[i][nums[i]]= true # as nums[i] can always be achieved # by taking only element # at index i that is nums[i] for i in range(n): dp[i][nums[i]] = True for i in range(n): for j in range(target+1): # check if we can take previous row if (i - 1 >= 0): dp[i][j] = dp[i - 1][j] or dp[i][j] # check for row-2 if (i - 2 >= 0 and j >= nums[i]): dp[i][j] = dp[i - 2][j - nums[i]] or dp[i][j] return dp[n - 1][target] # Driver code nums = [ 1, 2, 2, 3 ] target = 4 print(subsetSumNonAdjacent(nums, target)) # This code is contributed by shinjanpatra
C#
// C# program to implement above approach
using System;
class GFG {
static bool subsetSumNonAdjacent(int[] nums, int target)
{
// size of the array
int n = nums.Length;
// Boolean dp table fill with false
bool[, ] dp = new bool[n, target + 1];
for (int i = 0; i < n; i++) {
for (int j = 0; j < target + 1; j++) {
dp[i, j] = false;
}
}
// Base Case
// Initialize dp[i][0]= true
// as 0 can always be achieved
// by not taking anything
for (int i = 0; i < n; i++) {
dp[i, 0] = true;
}
// Initialize dp[i][nums[i]]= true
// as nums[i] can always be achieved
// by taking only element
// at index i that is nums[i]
for (int i = 0; i < n; i++) {
dp[i, nums[i]] = true;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j <= target; j++) {
// check if we can take previous row
if (i - 1 >= 0) {
dp[i, j] = dp[i - 1, j] || dp[i, j];
}
// check for row-2
if (i - 2 >= 0 && j >= nums[i]) {
dp[i, j] = dp[i - 2, j - nums[i]]
|| dp[i, j];
}
}
}
return dp[n - 1, target];
}
// Driver code
public static void Main()
{
int[] nums = { 1, 2, 2, 3 };
int target = 4;
Console.Write(subsetSumNonAdjacent(nums, target));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript program to implement above approach
function subsetSumNonAdjacent(nums,target)
{
// size of the array
let n = nums.length;
// Boolean dp table fill with false
let dp = new Array(n);
for(let i=0;i<n;i++)
dp[i] = new Array(target + 1).fill(false);
// Base Case
// Initialize dp[i][0]= true
// as 0 can always be achieved
// by not taking anything
for (let i = 0; i < n; i++) {
dp[i][0] = true;
}
// Initialize dp[i][nums[i]]= true
// as nums[i] can always be achieved
// by taking only element
// at index i that is nums[i]
for (let i = 0; i < n; i++) {
dp[i][nums[i]] = true;
}
for (let i = 0; i < n; i++) {
for (let j = 0; j <= target; j++) {
// check if we can take previous row
if (i - 1 >= 0) {
dp[i][j]
= dp[i - 1][j] || dp[i][j];
}
// check for row-2
if (i - 2 >= 0 && j >= nums[i]) {
dp[i][j]
= dp[i - 2][j - nums[i]]
|| dp[i][j];
}
}
}
return dp[n - 1][target];
}
// Driver code
let nums = [ 1, 2, 2, 3 ]
let target = 4
document.write(subsetSumNonAdjacent(nums, target));
// This code is contributed by shinjanpatra
</script>
Producción
true
Complejidad de tiempo : O(N*objetivo)
Espacio auxiliar : O(N*objetivo)