Given an array nums[ ] and an integer target. Find whether there exists a combination of integers in nums[ ] such that their sum is equal to target and none of those elements are adjacent in the original array.
Example :
Input : nums[ ] = [1, 2, 2, 3], target = 4
Output : true
Explanation : We can pick [1, 3] since they are non-adjacent and sums to 4Input : nums[ ] = [1, 3, 1], target = 4
Output: false
Explanation : We can’t pick [1, 3] or [3, 1] since they are adjacent.
Approach: The problem can be solved using Dynamic Programming as per below steps:
- dp[i][j]: Create a 2-d dp array that stores if it is possible to achieve a sum of exactly j after considering the first i elements from the array.
- At a given index i and a given sum j there can be two cases:
- Either we can include the current number, nums[i], or we don’t.
- If we don’t include the current number, we simply look back to the previous row of the dp.
- If we do include the current number, we have to look back two rows in the dp array, because no adjacent elements can be selected.
- So once we select element i we can ignore element i-1 since it can’t be taken.
- Base Case:
- Initially initialize the boolean dp table with false.
- Then, fill true in first column as sum 0 can always be achieved by not taking any element.
- Also fill dp[i][nums[i]] with true values, which indicates that we can achieve a sum of nums[i] after considering the first i elements from the array (which is obvious just take the element at index i).
- Transition states:
- Case 1: dp[i][j] = dp[i – 1][j] || dp[i][j]
- check the value at previous row
- if it is true then we can make the subset sum equal to target by taking elements till the last row,
- So make dp[i][j] true as well
- Case 2: dp[i][j] = dp[i – 2][j – nums[i]] || dp[i][j]
- check if we add the current element nums[i] to the current row – 2 (as it is not adjacent) dp table and make the sum equal to target.
- Case 1: dp[i][j] = dp[i – 1][j] || dp[i][j]
Illustration:
Consider the example where nums[ ] = [1, 2, 2, 3], target = 4
The dp table would look like the following (i represents nums[i] and j represent target)
i (nums[i]) \ j (target) 0 1 2 3 4 0 (nums[0]=1) true true false false false 1 (nums[1]=2) true true true false false 2 (nums[2]=2) true true true true false 3 (nums[2]=3) true true true true true
Below is the implementation of the above approach:
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 codeint 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 approachdef 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 codenums = [ 1, 2, 2, 3 ]target = 4print(subsetSumNonAdjacent(nums, target))# This code is contributed by shinjanpatra |
C#
// C# program to implement above approachusing 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 approachfunction 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 codelet nums = [ 1, 2, 2, 3 ]let target = 4document.write(subsetSumNonAdjacent(nums, target));// This code is contributed by shinjanpatra</script> |
Output
true
Time Complexity: O(N*target)
Auxiliary Space: O(N*target)
Another Approach ( Time and Space Optimization): we can use Binary search and Vector of pair in these way:
1. First store the element of array and their index in vector of pair. 2. Then we will sort vector of pair for binary search . 3. Then we will iterate whole array and our Newtarget will be ‘target -arr[i]’ . If Newtarget exists in array ,Then we will find index of first and last occurrence of Newtarget using binary search 4. Then check all the index in the range from firstocc to lastocc , if the index of Newtarget and arr[i] is adjacent or not using vector of pair. If it is not adjacent . Then we will return true. If we have not found any index of that type by iterating whole array.Then return false .
Below is the implementation of the above approach :
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to Find the index of first occurrence of targetint Firstocc(vector<pair<int, int>> &vec, int target) { int l = 0, h = vec.size() - 1 , index=-1; while (l <= h) { int mid = (l + h) / 2; // Updating index of target if(vec[mid].first == target){ index = mid; } if (vec[mid].first >= target) { h = mid - 1; }//Because we want to find first occ else { l = mid + 1; } } return index;}// Function to Find the index of last occurrence of targetint Lastocc(vector<pair<int, int>> &vec, int target) { int l = 0, h = vec.size() - 1 , index=-1; while (l <= h) { int mid = (l + h) / 2; // Updating index of target if(vec[mid].first == target){ index = mid; } if (vec[mid].first <= target) { l = mid + 1;}//Because we want to find last occ else { h = mid - 1; } } return index;}// Function to Check if there exists a non-adjacent // pair with given sumbool subsetSumNonAdjacent( vector<int>& nums, int target){ // size of the array int n = nums.size(); // vector of pair for storing value and index of value vector<pair<int, int>> vec; for(int i=0 ;i < n ;i++) { vec.push_back(make_pair(nums[i], i)); } sort(vec.begin(),vec.end());// sort vec for Binary search for(int i= 0 ; i < n ;i++) { // our target will be Newtarget int Newtarget = target - vec[i].first; int Firstindex=Firstocc(vec , Newtarget ); int Lastindex=Lastocc(vec , Newtarget ); //checking if target exist in vec or not if(Firstindex >=0 && Lastindex>=0 ) { int pos = vec[i].second;// position in nums vector // At max four iteration Because we can get our answer in it for(int j=Firstindex; j< 4 && j<= Lastindex;j++) { int currpos = vec[j].second;// position in nums vector // checking if it is a adjacent pair or not if(pos != currpos && pos-1 != currpos && pos+1 != currpos) { return true; } } } } return false ;}// Driver codeint main(){ vector<int> nums = { 1, 2, 2, 3 }; int target = 4; //Function call if(subsetSumNonAdjacent(nums, target)) { cout<<"true"; } else{ cout<<"false"; } return 0;}// This Approach is contributed by nikhilsainiofficial546 |
Java
// Python program for the above approach// Function to Find the index of first occurrence of targetimport java.util.Arrays;public class Main { // Function to Find the index of first occurrence of // target public static int firstOcc(int[][] vec, int target) { int l = 0; int h = vec.length - 1; int index = -1; while (l <= h) { int mid = (l + h) / 2; // Updating index of target if (vec[mid][0] == target) { index = mid; } if (vec[mid][0] >= target) { h = mid - 1; // Because we want to find // first occ } else { l = mid + 1; } } return index; } // Function to Find the index of last occurence of // target public static int lastOcc(int[][] vec, int target) { int l = 0; int h = vec.length - 1; int index = -1; while (l <= h) { int mid = (l + h) / 2; // Updating index of target if (vec[mid][0] == target) { index = mid; } if (vec[mid][0] <= target) { l = mid + 1; // Because we want to find last occ } else { h = mid - 1; } } return index; } // Function to Check if there exists a non-adjacent pair // with given sum public static boolean subsetSumNonAdjacent(int[] nums, int target) { // size of the array int n = nums.length; // list of tuples for storing value and index of // value int[][] vec = new int[n][2]; for (int i = 0; i < n; i++) { vec[i][0] = nums[i]; vec[i][1] = i; } Arrays.sort( vec, (a, b) -> Integer.compare( a[0], b[0])); // sort vec for Binary search for (int i = 0; i < n; i++) { // our target will be Newtarget int Newtarget = target - vec[i][0]; int firstIndex = firstOcc(vec, Newtarget); int lastIndex = lastOcc(vec, Newtarget); // checking if target exist in vec or not if (firstIndex >= 0 && lastIndex >= 0) { int pos = vec[i][1]; // position in nums list // At max four iteration Because we can get // our answer in it for (int j = firstIndex; j <= Math.min(4, lastIndex); j++) { int currPos = vec[j] [1]; // position in nums list // checking if it is a adjacent pair or // not if (pos != currPos && pos - 1 != currPos && pos + 1 != currPos) { return true; } } } } return false; } public static void main(String[] args) { int[] nums = { 1, 2, 2, 3 }; int target = 4; // Function call if (subsetSumNonAdjacent(nums, target)) { System.out.println("true"); } else { System.out.println("false"); } }}// This code is generated by Chetan Bargal |
Python3
# Python program for the above approach# Function to Find the index of first occurrence of targetdef Firstocc(vec, target): l = 0 h = len(vec) - 1 index = -1 while l <= h: mid = (l + h) // 2 # Updating index of target if vec[mid][0] == target: index = mid if vec[mid][0] >= target: h = mid - 1 # Because we want to find first occ else: l = mid + 1 return index# Function to Find the index of last occurrence of targetdef Lastocc(vec, target): l = 0 h = len(vec) - 1 index = -1 while l <= h: mid = (l + h) // 2 # Updating index of target if vec[mid][0] == target: index = mid if vec[mid][0] <= target: l = mid + 1 # Because we want to find last occ else: h = mid - 1 return index# Function to Check if there exists a non-adjacent pair with given sumdef subsetSumNonAdjacent(nums, target): # size of the array n = len(nums) # list of tuples for storing value and index of value vec = [(nums[i], i) for i in range(n)] vec = sorted(vec) # sort vec for Binary search for i in range(n): # our target will be Newtarget Newtarget = target - vec[i][0] Firstindex = Firstocc(vec, Newtarget) Lastindex = Lastocc(vec, Newtarget) # checking if target exist in vec or not if Firstindex >= 0 and Lastindex >= 0: pos = vec[i][1] # position in nums list # At max four iteration Because we can get our answer in it for j in range(Firstindex, min(4, Lastindex + 1)): currpos = vec[j][1] # position in nums list # checking if it is a adjacent pair or not if pos != currpos and pos - 1 != currpos and pos + 1 != currpos: return True return False# Driver codenums = [1, 2, 2, 3]target = 4# Function callif subsetSumNonAdjacent(nums, target): print("true")else: print("false") |
C#
// C# program for the above approachusing System;using System.Collections.Generic;using System.Linq;class GFG { // Function to Find the index of first occurrence of // target static int Firstocc(List<Tuple<int, int> > vec, int target) { int l = 0, h = vec.Count - 1, index = -1; while (l <= h) { int mid = (l + h) / 2; // Updating index of target if (vec[mid].Item1 == target) { index = mid; } if (vec[mid].Item1 >= target) { h = mid - 1; } // Because we want to find first occ else { l = mid + 1; } } return index; } // Function to Find the index of last occurrence of // target static int Lastocc(List<Tuple<int, int> > vec, int target) { int l = 0, h = vec.Count - 1, index = -1; while (l <= h) { int mid = (l + h) / 2; // Updating index of target if (vec[mid].Item1 == target) { index = mid; } if (vec[mid].Item1 <= target) { l = mid + 1; } // Because we want to find last occ else { h = mid - 1; } } return index; } // Function to Check if there exists a non-adjacent // pair with given sum static bool subsetSumNonAdjacent(List<int> nums, int target) { // size of the array int n = nums.Count; // List of Tuple for storing value and index of // value List<Tuple<int, int> > vec = new List<Tuple<int, int> >(); for (int i = 0; i < n; i++) { vec.Add(Tuple.Create(nums[i], i)); } vec.Sort(); // sort vec for Binary search for (int i = 0; i < n; i++) { // our target will be Newtarget int Newtarget = target - vec[i].Item1; int Firstindex = Firstocc(vec, Newtarget); int Lastindex = Lastocc(vec, Newtarget); // checking if target exist in vec or not if (Firstindex >= 0 && Lastindex >= 0) { int pos = vec[i] .Item2; // position in nums vector // At max four iteration Because we can get // our answer in it for (int j = Firstindex; j < 4 && j <= Lastindex; j++) { int currpos = vec[j].Item2; // position in nums // vector // checking if it is a adjacent pair or // not if (pos != currpos && pos - 1 != currpos && pos + 1 != currpos) { return true; } } } } return false; } // Driver code static void Main(string[] args) { List<int> nums = new List<int>{ 1, 2, 2, 3 }; int target = 4; // Function call if (subsetSumNonAdjacent(nums, target)) { Console.WriteLine("true"); } else { Console.WriteLine("false"); } }} |
Javascript
// javascript program for the above approach// Function to Find the index of first occurrence of targetfunction Firstocc(vec, target) { let l = 0, h = vec.length - 1 , index=-1; while (l <= h) { let mid = Math.floor((l + h) / 2); // Updating index of target if(vec[mid][0] == target){ index = mid; } if (vec[mid][0] >= target) { h = mid - 1; }//Because we want to find first occ else { l = mid + 1; } } return index;}// Function to Find the index of last occurrence of targetfunction Lastocc(vec, target) { let l = 0, h = vec.length - 1 , index=-1; while (l <= h) { let mid = Math.floor((l + h) / 2); // Updating index of target if(vec[mid][0] == target){ index = mid; } if (vec[mid][0] <= target) { l = mid + 1;}//Because we want to find last occ else { h = mid - 1; } } return index;}// Function to Check if there exists a non-adjacent // pair with given sumfunction subsetSumNonAdjacent(nums, target){ // size of the array let n = nums.length; // vector of pair for storing value and index of value let vec = []; for(let i=0 ;i < n ;i++) { vec.push([nums[i], i]); } vec.sort(function(a, b){ if(a[0] != b[0]){ return a[0] - b[0]; } return a[1] - b[1]; }); for(let i= 0 ; i < n ;i++) { // our target will be Newtarget let Newtarget = target - vec[i][0]; let Firstindex=Firstocc(vec , Newtarget ); let Lastindex=Lastocc(vec , Newtarget ); //checking if target exist in vec or not if(Firstindex >=0 && Lastindex>=0 ) { let pos = vec[i][1];// position in nums vector // At max four iteration Because we can get our answer in it for(let j=Firstindex; j< 4 && j<= Lastindex;j++) { let currpos = vec[j][1];// position in nums vector // checking if it is a adjacent pair or not if(pos != currpos && pos-1 != currpos && pos+1 != currpos) { return true; } } } } return false ;}// Driver codelet nums = [1, 2, 2, 3];let target = 4;// Function callif(subsetSumNonAdjacent(nums, target)){ console.log("true");}else{ console.log("false");}// This Approach is contributed by Nidhi goel. |
Output
true
Time Complexity: O(n * log n * 4) , we can also reduce it to O(n * log n) by writing conditions , instead using loop.
Auxiliary Space: O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
